2020-05-26 19:51:48

Author: Cedric Huchuan Xia (email, github)

Affiliation: Penn Lifespan Informatics and Neuroimaging Center (PennLINC)


This GPS Footprinting project is inspired by Finn et al. Nat Neuro (2015) and Kaufmann et al. Nat Neuro (2015). These authors studied how personal differences in functional brain connectivity can identify individuals, mature during development, alter in neuropsychiatric illness, and differ between genders. The authors referred to these individual differences as brain fingerprinting.

Here, we apply the fingerprinting technique to highly sampled GPS data in a clinical sample of youth. We are interested in how their individual mobility patterns can distinguish one another’s identity, differ between genders, and alter in psychopathological groups. In other words, can our footprint tell us apart and something about our behavior?

GPS data preprocessing was performed according to Ian Barnett’s imputation algorithm, originally published in Biostatistics (2020).

1. Setup Environment

require(ggplot2)
require(summarytools)
require(cowplot)
require(caret)
require(corrplot)
require(RColorBrewer)
require(vembedr)
require(Rmisc)
require(varian)
source('~/Documents/GitHub/SmartphoneSensorPipeline/Extra/plotting_functions.R')
project_path = "~/Documents/xia_gps/"
data_path = file.path(project_path,"beiwe_output_043020")

gps_df_path = file.path(data_path,"Processed_Data/Group/feature_matrix.txt")

2. GPS Features

The current data has 41 subjects, consisting of 3317 total days, and 15 GPS features. To conserve battery life, a subject’s GPS coordinates were tracked for in a 2-min-on and 18-min-off cycle everyday using their own mobile device via the Beiwe platform. We used Ian Barnett’s algorithm to impute the missing data during the off cycles. Assuming no more data was missing due to various factors, one would generate 144 mins of GPS data per day, or 10% of total minutes in a day.

As you can see from the figure below, we can nicely reconstruct an individuals’ mobility trajectory from these data.
gps_track Figure 1: A weekly view of a subject’s mobility pattern

For an even more intuitive view of the GPS data, take a look at the video here:





From these GPS traces, we extracted daily mobility features, such as max home distance, circadian routine, probability of pauses, as described in Barnett et al., Biostatistics (2020) and defined mathematically in its supplementary material.

To get a flavor of what these features look like, the first six days of GPS data for a subject are attached below.

gps_df = read.table(gps_df_path,header = T, dec = ",", )[,c(1,2,97:111)]

#Define the column types
gps_df$Date = as.Date(gps_df$Date)
gps_df[,3:dim(gps_df)[2]] = apply(gps_df[,3:dim(gps_df)[2]], 2, function(x) as.numeric(x))
head(gps_df)
NA

3. Exclude Data

The first step before further analysis is to exclude data points (days) that had excessive amount of data missing. Here is a historgram of the minutes missing for all 3317 total days.

p=minMiss_histplot(gps_df,200, "All Data")
ggplotly(p)

Figure 2: Minutes missing for all collected days. There are 3317 total days. Dashlines indicate the corresponding percentile.

3a. remove first and last days

First, we will remove the first and last days from each subject, because the application was installed during mid-day at the beginning of the study and uninstalled mid-day at the end of the study.

# loop through each subj to remove 1st and last days of gps data
gps_df_clean = data.frame() #initiate a df
for (subj in unique(gps_df$IID)){ #loop through each subj
  gps_df_subj <- subset(gps_df, IID == subj) #get gps_df per subject
  gps_df_subj <- gps_df_subj[2:(dim(gps_df_subj)[1]-1),] #remove the 1st and last days
  gps_df_clean <- rbind(gps_df_clean,gps_df_subj) #combine all subjs
}

This step removed 82 days. Now, dataset has 41 subjects, consisting of 3235 total days, and 15 GPS features.

Warning messages:
1: In readChar(file, size, TRUE) : truncating string with embedded nuls
2: In readChar(file, size, TRUE) : truncating string with embedded nuls
3: In readChar(file, size, TRUE) : truncating string with embedded nuls
4: In readChar(file, size, TRUE) : truncating string with embedded nuls

Figure 3: Minutes missing after removing the first and last days of each subject. There are 3235 total days. Dashlines indicate the corresponding percentile.

3b. remove days at the sensitivity threshold

Next, we are removing the days with excessive data missingness. This is of course an arbitrary step. Therefore we will conduct a sensitivity analysis of the missingness threshold we set by performing the analysis across multiple different thresholds. For now, the current sensitivity cutoff is set at 1440, which amounts to only excluding those with 100% of GPS missing.

sensitivity_cutoff = 1440 # this controls the cutoff threshold
gps_df_clean2 = subset(gps_df_clean, MinsMissing < sensitivity_cutoff)

This step removed 79 days. Now, dataset has 41 subjects, consisting of 3156 total days, and 16 GPS features.

Warning messages:
1: In readChar(file, size, TRUE) : truncating string with embedded nuls
2: In readChar(file, size, TRUE) : truncating string with embedded nuls
3: In readChar(file, size, TRUE) : truncating string with embedded nuls
4: In readChar(file, size, TRUE) : truncating string with embedded nuls

Figure 4: Minutes missing after removing days with all data missing. There are 3156 total days. Dashlines indicate the corresponding percentile.

Warning messages:
1: In readChar(file, size, TRUE) : truncating string with embedded nuls
2: In readChar(file, size, TRUE) : truncating string with embedded nuls
3: In readChar(file, size, TRUE) : truncating string with embedded nuls
4: In readChar(file, size, TRUE) : truncating string with embedded nuls

Figure 5: A Zoom-in plot of minutes missing distribution after removing days with all data missing. There are 3156 total days. Dashlines indicate the corresponding percentile.

4. Random Data Partitions

To operationalize individual footprinting prediction, we randomly split each individual’s available GPS data to two half partitions for 100 times. We used the features from the first half to determine if we can identify the same individual using their data in the second unseen half. Again, to avoid any (un)lucky random splits, we repeated data partition 100 times.

set.seed(510)
subj_seq = list()
part_times = 100
for (subj in unique(gps_df_clean2$IID)){
  subj_data = subset(gps_df_clean2, IID==subj)
  subj_seq[[subj]] <-createDataPartition(subj_data$IID,times = part_times, p =0.5)
}

5. Build Correlation Matrix

Here, similar to Finn et al. Nat Neuro (2015) and Kaufmann et al. Nat Neuro (2015), we built a Pearson correlation matrix among 16 available GPS features. Below is an illustrative sample of the variables and their correlations.

# an example of subj 1, and first half
Warning messages:
1: In readChar(file, size, TRUE) : truncating string with embedded nuls
2: In readChar(file, size, TRUE) : truncating string with embedded nuls
3: In readChar(file, size, TRUE) : truncating string with embedded nuls
4: In readChar(file, size, TRUE) : truncating string with embedded nuls
example_data = gps_df_clean2[subj_seq$`14w5qlo8`$Resample001,3:17]
gps_cor = rquery.cormat(example_data, type = "full")

Figure 6: Correlation matrix of GPS features for a subject.

We then calculated the feature matrix for all 41 subjects in the dataset, seperately for each half data partition, and for each random split.

make_feature_matrix = function(gps_df) {
  subj_mat_1 = list()
  subj_mat_2 = list()
  for (subj in unique(gps_df$IID)){
    subj_data = subset(gps_df_clean2, IID==subj)
    subj_mat_1[[subj]] = lapply(subj_seq[[subj]], function(list) rquery.cormat(subj_data[list,3:17], type = "flatten", graph = F)$r)
    subj_mat_2[[subj]] = lapply(subj_seq[[subj]], function(list) rquery.cormat(subj_data[-list,3:17], type = "flatten", graph = F)$r)
  }
  return(list(subj_mat_1 = subj_mat_1, subj_mat_2 = subj_mat_2 ))
}

gps_clean2_feature = make_feature_matrix(gps_df_clean2)

6. Match Target

Next we tried to match each target, defined by one subject’s feature matrix in the first half, to a feature matrix in the second half in the same random split. If the same individual’s feature matrix in the second half had the highest correlation among all subjects, then we assigned the match result 1, indicating a succussful match, otherwise 0, indicating an unsccussful match.

# creating a "database" against which target is to be matched with
subj_mat_1 = gps_clean2_feature$subj_mat_1
subj_mat_2 = gps_clean2_feature$subj_mat_2

calc_match_cor = function(subj_mat_1,subj_mat_2) {
  database = list() 
  for (time in 1:part_times) {
      database[[time]] = lapply(subj_mat_2, function(subjmat) subjmat[[time]]$cor)
  }
  
    # match target to database
    match_cor = list()
    for (subj1 in names(subj_mat_1)){ #loop through each subj
      # create a list of target across partitions
      target_list = lapply(subj_mat_1[[subj1]], function(part) part$cor)
      # create a match list
      for (time in 1:part_times){
        target_subj_time = target_list[[time]] #loop through each partition
        for (subj2 in names(subj_mat_2)){ #loop everyone in 2nd half
          data_subj_time = subj_mat_2[[subj2]][[time]]$cor
          match_cor[[subj1]][[as.character(time)]][[subj2]] = cor(target_subj_time,data_subj_time,use = "na.or.complete")
        }
      }
    }
  return(match_cor)
}

match_cor = calc_match_cor(subj_mat_1,subj_mat_2)

By tallying up all the successful and unsuccessful matchs in each of the 100 random splits, we calculated a distribution of match accuracy.

calc_acc_time=function(match_cor,part_times) {
  acc_time = array()
  for (time in 1:part_times){
    acc_time[time] = 0
    for (subj in names(subj_mat_1)){
      max_position = which.max(unlist(match_cor[[subj]][[as.character(time)]]))
      predicted_subj = names(subj_mat_1)[max_position]
      if (predicted_subj == subj) {
        acc_time[time] = acc_time[time] + 1
      }
    }
  }
  acc_time = acc_time/length(names(subj_mat_1))
  return(acc_time)
}
acc_time = calc_acc_time(match_cor,part_times)

Over the 100 random splits, the mean match accuracy was 55.02%, with a standard deviation of 5.9%, high of 70.73%, and low of 36.59%, (95%CI: 0.54-0.56).

p_time_cor = hist_chx(acc_time, bins = 15, title = paste("Correlated Features: \n Average Accuracy Across",part_times,"Data Partitions"), xaxis = "Prediction Accuracy", yaxis = "Count")
ggplotly(p_time_cor)

Figure 7: Match accuracy distributon across 100 data splits. Mean match accuracy was 0.55 (95%CI: 0.54-0.56)

calc_acc_subj = function(match_cor, part_times){
  acc_subj = array()
  for (subj in names(subj_mat_1)){
    acc_subj[subj] = 0
    for (time in 1:part_times){
      max_position = which.max(unlist(match_cor[[subj]][[as.character(time)]]))
      predicted_subj = names(subj_mat_1)[max_position]
      if (predicted_subj == subj) {
        acc_subj[subj] = acc_subj[subj] + 1
      }
    }
  }
  acc_subj = acc_subj/part_times
  acc_subj = acc_subj[-1]
  return(acc_subj)
}
acc_subj = calc_acc_subj(match_cor, part_times)

In addition to the match accuracy across subjects, we also calculated the match accuracy for each individual. Across the 41 subjects, the mean match accuracy was 55.02%, with a standard deviation of 30.19%, high of 98%, and low of 4%.

subj_scatter  = function(gps_df, acc_subj_vector, method){
  subj_df <- data.frame(x=unique(gps_df$IID))
  subj_df$y = acc_subj_vector
  subj_df = subj_df[order(subj_df$y),]
  subj_acc_plot = ggplot(subj_df) + 
  geom_point(aes(x = reorder(x, y), y = y)) + 
   theme_cowplot() + 
    labs(title = paste(method,"Features \n Subject Level Accuracy Across",part_times,"Data Partitions"), 
       x = "Subjects", y = "Prediction Accuracy") +
   theme(axis.text.x = element_text(angle = 45, hjust = 1, size = 8), plot.title = element_text(hjust = 0.5))
  return(subj_acc_plot)
}

ggplotly(subj_scatter(gps_df_clean2,acc_subj, "Correlated"))

Figure 8: Match accuracy distributon across 41 subjects. Mean match accuracy was 55.02%, with a standard deviation of 30.19%, high of 98%, and low of 4%. This shows dramatic differences in individual footprinting distinctiveness.

7. Permutation Test

To assess the statistical significance of the results above, we conducted a non-parametric permutation test. To do this, we randomly scrambled pair-wise subject-to-day linkage. We repeated this process 1000 times, and followed the same procedure as above to obtain a null distribution of average match accuracy across sample, and for each individual.

gps_df_perm = gps_df_clean2
perm_time = 1000
perm_acc_time = list()
perm_acc_subj = list()
for (i in 1:perm_time) {
  perm_part_times = 1
  print(paste("processing ...", i,"..."))
  gps_df_perm$IID = sample(gps_df_perm$IID)
  perm_subj_seq = make_subj_seq(gps_df_perm,part_times = perm_part_times)
  perm_gps = make_feature_matrix(gps_df_perm,perm_subj_seq)
  perm_mat_1 = perm_gps$subj_mat_1
  perm_mat_2 = perm_gps$subj_mat_2
  perm_match_cor = calc_match_cor(perm_mat_1,perm_mat_2)
  perm_acc_time[[i]] = calc_acc_time(perm_match_cor,part_times = perm_part_times)
  perm_acc_subj[[i]] = calc_acc_subj(perm_match_cor,part_times = perm_part_times)
}

Over the 1000 permutations, the mean match accuracy was 2.31%, with a standard deviation of 2.31%, high of 400%, and low of 2.3146341%.(95%CI: 0.02-0.02)

perm_acc_time_all = unlist(perm_acc_time)
q_time_cor = hist_chx(perm_acc_time_all, bins = 8, title = paste("Average Accuracy Across",length(perm_acc_time_all),"Permutations"), xaxis = "Prediction Accuracy", yaxis = "Count")
ggplotly(q_time_cor)

Figure 9: Match accuracy distributon across 1000 permutations. Mean match accuracy in permutation was 0.02 (95%CI: 0.02-0.02). This null distribution does not overlapp with the distributon using real data (Fig.7) at all.

We also calculated null distribution of match accuracy for each subject. Over the 1000 permutations, the mean match accuracy was 2.31%, with a standard deviation of 0.74%, high of 3.7%, and low of 0.6%.

perm_subj = list()
for (subj in subj_acc_plot$data$x) {
  perm_subj$val[[subj]] = sapply(perm_acc_subj, function(perm) perm[which(names(perm) == subj)])
  perm_subj$hist[[subj]] = hist_chx(perm_subj[[subj]]$val, bins = 8, title = paste(subj,": Accuracy Across \n",perm_time,"Permutations"), xaxis = "Prediction Accuracy", yaxis = "Count")
  perm_subj$acc[[subj]] = sum(perm_subj$val[[subj]])/perm_time
}
subj_df <- data.frame(x=unique(gps_df_clean2$IID))
subj_df$y = acc_subj
subj_df$y_perm = unlist(perm_subj$acc)
subj_df = subj_df[order(subj_df$y),]
p_subj_cor_perm = ggplot(subj_df, aes(x = reorder(x, y), y = value)) + 
  geom_point(aes(y = y, col = "subject data")) + 
  geom_point(aes(y = y_perm, col = "permutation")) +
  theme_cowplot() + 
  labs(title = paste("Cor Features \n Subject Level Accuracy Across",part_times,"Data Partitions"), 
       x = "Subjects", y = "Prediction Accuracy") +
  theme(axis.text.x = element_text(angle = 45, hjust = 1, size = 8), plot.title = element_text(hjust = 0.5))
ggplotly(p_subj_cor_perm)

Figure 8: Match accuracy null distributon across 41 subjects. Mean match accuracy in permutation was 2.31%, with a standard deviation of 0.74%, high of 3.7%, and low of 0.6%. While individuals exhibited marked differences in footprinting distinctivenss, the subject with the lowest prediction accuracy was still statistically significant against the permutation test (i.e. for subject bkq7uyp6: data: 4 % vs. permutation: 0.6%).

8. Mean Features

We calculated the mean of each GPS feature as a metric of feature variability. Similar to above, we calculated mean separately for each data partition and for each individual.

mean_gps = function(gps_df){
  mean_list = sapply(3:17,function(i) mean(gps_df[,i],na.rm=T))
  names(mean_list) = colnames(gps_df)[3:17]
  return(mean_list)
}

make_feature_mean = function(gps_df, subj_seq) {
  subj_mat_1 = list()
  subj_mat_2 = list()
  for (subj in unique(gps_df$IID)){
    subj_data = subset(gps_df_clean2, IID==subj)
    subj_mat_1[[subj]] = lapply(subj_seq[[subj]], function(list) mean_gps(subj_data[list,]))
    subj_mat_2[[subj]] = lapply(subj_seq[[subj]], function(list) mean_gps(subj_data[-list,]))
  }
  return(list(subj_mat_1 = subj_mat_1, subj_mat_2 = subj_mat_2 ))
}

gps_clean2_mean_feat = make_feature_mean(gps_df_clean2, subj_seq)

Figure 9: Feature mean across all subjects. The histogram are for data in the first random half split.

9. Variability Features

We calculated the root mean square of successive differences or RMSSD of each GPS feature as a metric of feature variability. Similar to above, we calculated RMSSD separately for each data partition and for each individual.

rmssd_gps = function(gps_df){
  rmssd_list = sapply(3:17,function(i) rmssd_id(gps_df[,i], gps_df$IID,long=F))
  names(rmssd_list) = colnames(gps_df)[3:17]
  return(rmssd_list)
}

make_feature_rmssd = function(gps_df, subj_seq) {
  subj_mat_1 = list()
  subj_mat_2 = list()
  for (subj in unique(gps_df$IID)){
    subj_data = subset(gps_df_clean2, IID==subj)
    subj_mat_1[[subj]] = lapply(subj_seq[[subj]], function(list) rmssd_gps(subj_data[list,]))
    subj_mat_2[[subj]] = lapply(subj_seq[[subj]], function(list) rmssd_gps(subj_data[-list,]))
  }
  return(list(subj_mat_1 = subj_mat_1, subj_mat_2 = subj_mat_2 ))
}

gps_clean2_rmssd_feat = make_feature_rmssd(gps_df_clean2, subj_seq)

Figure 10: Feature variability for all subjects. Variability is measured by root mean square of successive differences (RMSSD). The histograms are for data in the first random half split.

10. Predict with New Features

match_mean = calc_match_vector(gps_clean2_mean_feat$subj_mat_1,gps_clean2_mean_feat$subj_mat_2)
acc_time_mean = calc_acc_time(match_mean,part_times)
acc_subj_mean = calc_acc_subj(match_mean, part_times)
match_rmssd = calc_match_vector(gps_clean2_rmssd_feat$subj_mat_1,gps_clean2_rmssd_feat$subj_mat_2)
acc_time_rmssd = calc_acc_time(match_rmssd,part_times)
acc_subj_rmssd = calc_acc_subj(match_rmssd, part_times)

11. Permutation Tests with New Features

11a. Average Accuracy

perm_vector = function(gps_df, perm_time, method){
  gps_df_perm = gps_df
  perm_acc_time = list()
  perm_acc_subj = list()
  for (i in 1:perm_time) {
    perm_part_times = 1
    print(paste("processing ...", i,"..."))
    gps_df_perm$IID = sample(gps_df_perm$IID)
    perm_subj_seq = make_subj_seq(gps_df_perm,part_times = perm_part_times)
    if (method = "rmssd") {
Error: unexpected '=' in:
"    perm_subj_seq = make_subj_seq(gps_df_perm,part_times = perm_part_times)
    if (method ="
#perm_mean = perm_vector(gps_df_clean2, 1000, "mean")


p_time_mean = hist_chx(acc_time_mean, bins = 8, title = paste("Mean Features: \n Average Accuracy Across",length(acc_time_mean),"Data Partitions"), xaxis = "Prediction Accuracy", yaxis = "Count")

q_time_mean =  hist_chx(unlist(perm_mean$perm_acc_time), bins = 8, title = paste("Mean Features: \n Average Accuracy Across",length(perm_mean$perm_acc_time),"Permutations"), xaxis = "Prediction Accuracy", yaxis = "Count")

p_time_mean + q_time_mean

#perm_rmssd = perm_vector(gps_df_clean2, 1000, "rmssd")

p_time_rmssd = hist_chx(acc_time_rmssd, bins = 8, title = paste("RMSSD Features: \n Average Accuracy Across",length(acc_time_rmssd),"Data Partitions"), xaxis = "Prediction Accuracy", yaxis = "Count")

q_time_rmssd = hist_chx(unlist(perm_rmssd$perm_acc_time), bins = 8, title = paste("RMSSD Features: Average Accuracy Across",length(perm_mean$perm_acc_time),"Permutations"), xaxis = "Prediction Accuracy", yaxis = "Count")

p_time_rmssd + q_time_rmssd


combine_perm_subj = function(acc_subj_plot, perm_acc_subj) {
  perm_subj = list()
  for (subj in acc_subj_plot$data$x) {
    perm_subj$val[[subj]] = sapply(perm_acc_subj, function(perm) perm[which(names(perm) == subj)])
    perm_subj$hist[[subj]] = hist_chx(perm_subj[[subj]]$val, bins = 8, title = paste(subj,": Accuracy Across \n",perm_time,"Permutations"), xaxis = "Prediction Accuracy", yaxis = "Count")
    perm_subj$acc[[subj]] = sum(perm_subj$val[[subj]])/perm_time
  }
  return(perm_subj)
}


subj_scatter_perm = function(gps_df,acc_subj,perm_subj, method){
    subj_df <- data.frame(x=unique(gps_df$IID))
  subj_df$y = acc_subj
  subj_df$y_perm = unlist(perm_subj$acc)
  subj_df = subj_df[order(subj_df$y),]
  p = ggplot(subj_df, aes(x = reorder(x, y), y = value)) + 
    geom_point(aes(y = y, col = "subject data")) + 
    geom_point(aes(y = y_perm, col = "permutation")) +
    theme_cowplot() + 
    labs(title = paste(method,"Features \n Subject Level Accuracy Across",part_times,"Data Partitions"), 
         x = "Subjects", y = "Prediction Accuracy") +
    theme(axis.text.x = element_text(angle = 45, hjust = 1, size = 8), plot.title = element_text(hjust = 0.5))
  return(p)
}
p_subj_mean = subj_scatter(gps_df_clean2, acc_subj_mean, "Mean")
perm_subj_mean = combine_perm_subj(p_subj_mean,perm_mean$perm_acc_subj)
p_subj_mean_perm = subj_scatter_perm(gps_df_clean2, acc_subj_mean, perm_subj_mean, "Mean")
ggplotly(p_subj_mean_perm)
p_subj_rmssd = subj_scatter(gps_df_clean2, acc_subj_rmssd, "RMSSD")
perm_subj_rmssd = combine_perm_subj(p_subj_rmssd,perm_rmssd$perm_acc_subj)
p_subj_rmssd_perm = subj_scatter_perm(gps_df_clean2, acc_subj_rmssd, perm_subj_rmssd, "RMSSD")
ggplotly(p_subj_rmssd_perm)

12. Compare Features

p_time_cor + p_time_mean + p_time_rmssd

p_subj_cor_perm / p_subj_mean_perm / p_subj_rmssd_perm

13. Combine Features

14. Misc Info

#sessionInfo()
LS0tCnRpdGxlOiAiR1BTIEZvb3RwcmludGluZyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBpbmNsdWRlczoKICAgICAgYWZ0ZXJfYm9keTogZm9vdGVyLmh0bWwKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6CiAgICAgIHRvY19jb2xsYXBzZWQ6IHllcwogIGh0bWxfZG9jdW1lbnQ6CiAgICBkZl9wcmludDogcGFnZWQKICAgIHRvYzogeWVzCmVkaXRvcl9vcHRpb25zOiAKICBjaHVua19vdXRwdXRfdHlwZTogaW5saW5lCi0tLQpgciBTeXMudGltZSgpYAoKQXV0aG9yOiBbQ2VkcmljIEh1Y2h1YW4gWGlhXShodHRwczovL3d3dy5wZW5ubGluYy5pby90ZWFtL0NlZHJpYy1IdWNodWFuLVhpYSkgKFtlbWFpbF0oaHhpYUB1cGVubi5lZHUpLCBbZ2l0aHViXShodHRwczovL2dpdGh1Yi5jb20vY2VkcmljeC8pKQoKQWZmaWxpYXRpb246IFBlbm4gTGlmZXNwYW4gSW5mb3JtYXRpY3MgYW5kIE5ldXJvaW1hZ2luZyBDZW50ZXIgKFtQZW5uTElOQ10ocGVubmxpbmMuaW8pKSAKCioqKgoKClRoaXMgKkdQUyBGb290cHJpbnRpbmcgcHJvamVjdCogaXMgaW5zcGlyZWQgYnkgW0Zpbm4gZXQgYWwuIE5hdCBOZXVybyAgKDIwMTUpXShodHRwczovL3d3dy5uYXR1cmUuY29tL2FydGljbGVzL25uLjQxMzUpIGFuZCBbS2F1Zm1hbm4gZXQgYWwuIE5hdCBOZXVybyAoMjAxNSldKGh0dHBzOi8vd3d3Lm5hdHVyZS5jb20vYXJ0aWNsZXMvczQxNTkzLTAxOS0wNDcxLTcpLiBUaGVzZSBhdXRob3JzIHN0dWRpZWQgaG93IHBlcnNvbmFsIGRpZmZlcmVuY2VzIGluIGZ1bmN0aW9uYWwgYnJhaW4gY29ubmVjdGl2aXR5IGNhbiBpZGVudGlmeSBpbmRpdmlkdWFscywgbWF0dXJlIGR1cmluZyBkZXZlbG9wbWVudCwgYWx0ZXIgaW4gbmV1cm9wc3ljaGlhdHJpYyBpbGxuZXNzLCBhbmQgZGlmZmVyIGJldHdlZW4gZ2VuZGVycy4gVGhlIGF1dGhvcnMgcmVmZXJyZWQgdG8gdGhlc2UgaW5kaXZpZHVhbCBkaWZmZXJlbmNlcyBhcyAqYnJhaW4gZmluZ2VycHJpbnRpbmcqLgoKPiBIZXJlLCB3ZSBhcHBseSB0aGUgZmluZ2VycHJpbnRpbmcgdGVjaG5pcXVlIHRvIGhpZ2hseSBzYW1wbGVkIEdQUyBkYXRhIGluIGEgY2xpbmljYWwgc2FtcGxlIG9mIHlvdXRoLiBXZSBhcmUgaW50ZXJlc3RlZCBpbiBob3cgdGhlaXIgaW5kaXZpZHVhbCBtb2JpbGl0eSBwYXR0ZXJucyBjYW4gZGlzdGluZ3Vpc2ggb25lIGFub3RoZXIncyBpZGVudGl0eSwgZGlmZmVyIGJldHdlZW4gZ2VuZGVycywgYW5kIGFsdGVyIGluIHBzeWNob3BhdGhvbG9naWNhbCBncm91cHMuIEluIG90aGVyIHdvcmRzLCBjYW4gb3VyIGZvb3RwcmludCB0ZWxsIHVzIGFwYXJ0IGFuZCBzb21ldGhpbmcgYWJvdXQgb3VyIGJlaGF2aW9yPyAKCkdQUyBkYXRhIHByZXByb2Nlc3Npbmcgd2FzIHBlcmZvcm1lZCBhY2NvcmRpbmcgdG8gW0lhbiBCYXJuZXR0J3MgaW1wdXRhdGlvbiBhbGdvcml0aG1dKGh0dHBzOi8vZ2l0aHViLmNvbS9pYW5qYW1lc2Jhcm5ldHQvU21hcnRwaG9uZVNlbnNvclBpcGVsaW5lKSwgb3JpZ2luYWxseSBwdWJsaXNoZWQgaW4gW0Jpb3N0YXRpc3RpY3MgKDIwMjApXShodHRwczovL2FjYWRlbWljLm91cC5jb20vYmlvc3RhdGlzdGljcy9hcnRpY2xlLWFic3RyYWN0LzIxLzIvZTk4LzUxNDU5MDgpLgoKIyMjIDEuIFNldHVwIEVudmlyb25tZW50IApgYGB7ciBsb2FkX2xpYiwgbWVzc2FnZT1GQUxTRX0KcmVxdWlyZShnZ3Bsb3QyKQpyZXF1aXJlKHN1bW1hcnl0b29scykKcmVxdWlyZShjb3dwbG90KQpyZXF1aXJlKGNhcmV0KQpyZXF1aXJlKGNvcnJwbG90KQpyZXF1aXJlKFJDb2xvckJyZXdlcikKcmVxdWlyZSh2ZW1iZWRyKQpyZXF1aXJlKFJtaXNjKQpyZXF1aXJlKHZhcmlhbikKcmVxdWlyZShwYXRjaHdvcmspCnNvdXJjZSgnfi9Eb2N1bWVudHMvR2l0SHViL1NtYXJ0cGhvbmVTZW5zb3JQaXBlbGluZS9FeHRyYS9wbG90dGluZ19mdW5jdGlvbnMuUicpCmBgYAoKCmBgYHtyIGRlZl9wYXRoc30KcHJvamVjdF9wYXRoID0gIn4vRG9jdW1lbnRzL3hpYV9ncHMvIgpkYXRhX3BhdGggPSBmaWxlLnBhdGgocHJvamVjdF9wYXRoLCJiZWl3ZV9vdXRwdXRfMDQzMDIwIikKZ3BzX2RmX3BhdGggPSBmaWxlLnBhdGgoZGF0YV9wYXRoLCJQcm9jZXNzZWRfRGF0YS9Hcm91cC9mZWF0dXJlX21hdHJpeC50eHQiKQpgYGAKCiMjIyAyLiBHUFMgRmVhdHVyZXMKVGhlIGN1cnJlbnQgZGF0YSBoYXMgYHIgbGVuZ3RoKHVuaXF1ZShncHNfZGYkSUlEKSlgIHN1YmplY3RzLCBjb25zaXN0aW5nIG9mIGByIGRpbShncHNfZGYpWzFdYCB0b3RhbCBkYXlzLCBhbmQgYHIgbGVuZ3RoKGNvbG5hbWVzKGdwc19kZikpLTJgIEdQUyBmZWF0dXJlcy4gVG8gY29uc2VydmUgYmF0dGVyeSBsaWZlLCBhIHN1YmplY3QncyBHUFMgY29vcmRpbmF0ZXMgd2VyZSB0cmFja2VkIGZvciBpbiBhIDItbWluLW9uIGFuZCAxOC1taW4tb2ZmIGN5Y2xlIGV2ZXJ5ZGF5IHVzaW5nIHRoZWlyIG93biBtb2JpbGUgZGV2aWNlIHZpYSB0aGUgW0JlaXdlIHBsYXRmb3JtXShodHRwczovL3d3dy5iZWl3ZS5vcmcpLiBXZSB1c2VkIFtJYW4gQmFybmV0dCdzIGFsZ29yaXRobV0oaHR0cHM6Ly9naXRodWIuY29tL2lhbmphbWVzYmFybmV0dC9TbWFydHBob25lU2Vuc29yUGlwZWxpbmUpIHRvIGltcHV0ZSB0aGUgbWlzc2luZyBkYXRhIGR1cmluZyB0aGUgb2ZmIGN5Y2xlcy4gQXNzdW1pbmcgbm8gbW9yZSBkYXRhIHdhcyBtaXNzaW5nIGR1ZSB0byB2YXJpb3VzIGZhY3RvcnMsIG9uZSB3b3VsZCBnZW5lcmF0ZSBgciAyKjMqMjRgIG1pbnMgb2YgR1BTIGRhdGEgcGVyIGRheSwgb3IgYHIgMi8yMCoxMDBgJSBvZiB0b3RhbCBtaW51dGVzIGluIGEgZGF5LiAKCkFzIHlvdSBjYW4gc2VlIGZyb20gdGhlIGZpZ3VyZSBiZWxvdywgd2UgY2FuIG5pY2VseSByZWNvbnN0cnVjdCBhbiBpbmRpdmlkdWFscycgbW9iaWxpdHkgdHJhamVjdG9yeSBmcm9tIHRoZXNlIGRhdGEuCjxjZW50ZXI+CiFbZ3BzX3RyYWNrXSguL2dwc190cmFja19zYW1wbGUucG5nKQoqKkZpZ3VyZSAxOiBBIHdlZWtseSB2aWV3IG9mIGEgc3ViamVjdCdzIG1vYmlsaXR5IHBhdHRlcm4qKgo8L2NlbnRlcj4KCkZvciBhbiBldmVuIG1vcmUgaW50dWl0aXZlIHZpZXcgb2YgdGhlIEdQUyBkYXRhLCB0YWtlIGEgbG9vayBhdCB0aGUgdmlkZW8gaGVyZToKCjxjZW50ZXI+CmBgYHtyIGVjaG89RkFMU0V9CmVtYmVkX3VybCgiaHR0cHM6Ly95b3V0dS5iZS9Lb2JFU2d0Zm9PbyIpCmBgYAo8L2NlbnRlcj4KCgogPGJyPjxicj48YnI+PGJyPgoKRnJvbSB0aGVzZSBHUFMgdHJhY2VzLCB3ZSBleHRyYWN0ZWQgZGFpbHkgbW9iaWxpdHkgZmVhdHVyZXMsIHN1Y2ggYXMgKm1heCBob21lIGRpc3RhbmNlKiwgKmNpcmNhZGlhbiByb3V0aW5lKiwgKnByb2JhYmlsaXR5IG9mIHBhdXNlcyosIGFzIGRlc2NyaWJlZCBpbiBbQmFybmV0dCBldCBhbC4sIEJpb3N0YXRpc3RpY3MgKDIwMjApXShodHRwczovL2FjYWRlbWljLm91cC5jb20vYmlvc3RhdGlzdGljcy9hcnRpY2xlLWFic3RyYWN0LzIxLzIvZTk4LzUxNDU5MDgpIGFuZCBkZWZpbmVkIG1hdGhlbWF0aWNhbGx5IGluIGl0cyBbc3VwcGxlbWVudGFyeSBtYXRlcmlhbF0oaHR0cHM6Ly9kcml2ZS5nb29nbGUuY29tL29wZW4/aWQ9MWpIRkpMWGpVU3dvc2VyTjV0UHRBLS1oOUdFY1ZmWjEwKS4KClRvIGdldCBhIGZsYXZvciBvZiB3aGF0IHRoZXNlIGZlYXR1cmVzIGxvb2sgbGlrZSwgdGhlIGZpcnN0IHNpeCBkYXlzIG9mIEdQUyBkYXRhIGZvciBhIHN1YmplY3QgYXJlIGF0dGFjaGVkIGJlbG93LiAKYGBge3IgcmVhZF9ncHN9Cmdwc19kZiA9IHJlYWQudGFibGUoZ3BzX2RmX3BhdGgsaGVhZGVyID0gVCwgZGVjID0gIiwiLCApWyxjKDEsMiw5NzoxMTEpXQoKI0RlZmluZSB0aGUgY29sdW1uIHR5cGVzCmdwc19kZiREYXRlID0gYXMuRGF0ZShncHNfZGYkRGF0ZSkKZ3BzX2RmWywzOmRpbShncHNfZGYpWzJdXSA9IGFwcGx5KGdwc19kZlssMzpkaW0oZ3BzX2RmKVsyXV0sIDIsIGZ1bmN0aW9uKHgpIGFzLm51bWVyaWMoeCkpCmhlYWQoZ3BzX2RmKQoKYGBgCgojIyMgMy4gRXhjbHVkZSBEYXRhClRoZSBmaXJzdCBzdGVwIGJlZm9yZSBmdXJ0aGVyIGFuYWx5c2lzIGlzIHRvIGV4Y2x1ZGUgZGF0YSBwb2ludHMgKGRheXMpIHRoYXQgaGFkIGV4Y2Vzc2l2ZSBhbW91bnQgb2YgZGF0YSBtaXNzaW5nLiBIZXJlIGlzIGEgaGlzdG9yZ3JhbSBvZiB0aGUgbWludXRlcyBtaXNzaW5nIGZvciBhbGwgYHIgZGltKGdwc19kZilbMV1gIHRvdGFsIGRheXMuIAoKYGBge3IgZWNobz1UUlVFLCBmaWcuaGVpZ2h0PTQsIGZpZy53aWR0aD0xMCwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KcD1taW5NaXNzX2hpc3RwbG90KGdwc19kZiwyMDAsICJBbGwgRGF0YSIpCmdncGxvdGx5KHApCmBgYAoqKkZpZ3VyZSAyOiBNaW51dGVzIG1pc3NpbmcgZm9yIGFsbCBjb2xsZWN0ZWQgZGF5cy4qKiBUaGVyZSBhcmUgYHIgZGltKGdwc19kZilbMV1gIHRvdGFsIGRheXMuIERhc2hsaW5lcyBpbmRpY2F0ZSB0aGUgY29ycmVzcG9uZGluZyBwZXJjZW50aWxlLgoKCgoKIyMjIyAzYS4gIHJlbW92ZSBmaXJzdCBhbmQgbGFzdCBkYXlzCkZpcnN0LCB3ZSB3aWxsIHJlbW92ZSB0aGUgZmlyc3QgYW5kIGxhc3QgZGF5cyBmcm9tIGVhY2ggc3ViamVjdCwgYmVjYXVzZSB0aGUgYXBwbGljYXRpb24gd2FzIGluc3RhbGxlZCBkdXJpbmcgbWlkLWRheSBhdCB0aGUgYmVnaW5uaW5nIG9mIHRoZSBzdHVkeSBhbmQgdW5pbnN0YWxsZWQgbWlkLWRheSBhdCB0aGUgZW5kIG9mIHRoZSBzdHVkeS4gCgpgYGB7ciAxc3RfbGFzdF9kYXlzfQojIGxvb3AgdGhyb3VnaCBlYWNoIHN1YmogdG8gcmVtb3ZlIDFzdCBhbmQgbGFzdCBkYXlzIG9mIGdwcyBkYXRhCmdwc19kZl9jbGVhbiA9IGRhdGEuZnJhbWUoKSAjaW5pdGlhdGUgYSBkZgpmb3IgKHN1YmogaW4gdW5pcXVlKGdwc19kZiRJSUQpKXsgI2xvb3AgdGhyb3VnaCBlYWNoIHN1YmoKICBncHNfZGZfc3ViaiA8LSBzdWJzZXQoZ3BzX2RmLCBJSUQgPT0gc3ViaikgI2dldCBncHNfZGYgcGVyIHN1YmplY3QKICBncHNfZGZfc3ViaiA8LSBncHNfZGZfc3VialsyOihkaW0oZ3BzX2RmX3N1YmopWzFdLTEpLF0gI3JlbW92ZSB0aGUgMXN0IGFuZCBsYXN0IGRheXMKICBncHNfZGZfY2xlYW4gPC0gcmJpbmQoZ3BzX2RmX2NsZWFuLGdwc19kZl9zdWJqKSAjY29tYmluZSBhbGwgc3VianMKfQpgYGAKClRoaXMgc3RlcCByZW1vdmVkIGByIGRpbShncHNfZGYpWzFdIC0gZGltKGdwc19kZl9jbGVhbilbMV1gIGRheXMuIE5vdywgZGF0YXNldCBoYXMgYHIgbGVuZ3RoKHVuaXF1ZShncHNfZGZfY2xlYW4kSUlEKSlgIHN1YmplY3RzLCBjb25zaXN0aW5nIG9mIGByIGRpbShncHNfZGZfY2xlYW4pWzFdYCB0b3RhbCBkYXlzLCBhbmQgYHIgbGVuZ3RoKGNvbG5hbWVzKGdwc19kZl9jbGVhbikpLTJgIEdQUyBmZWF0dXJlcy4KCmBgYHtyIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD00LCBlY2hvPUZBTFNFfQpwPW1pbk1pc3NfaGlzdHBsb3QoZ3BzX2RmX2NsZWFuLDIwMCwgIkFmdGVyIFJlbW92aW5nIDFzdCBhbmQgTGFzdCBEYXlzIikKZ2dwbG90bHkocCkKYGBgCioqRmlndXJlIDM6IE1pbnV0ZXMgbWlzc2luZyBhZnRlciByZW1vdmluZyB0aGUgZmlyc3QgYW5kIGxhc3QgZGF5cyBvZiBlYWNoIHN1YmplY3QuKiogVGhlcmUgYXJlIGByIGRpbShncHNfZGZfY2xlYW4pWzFdYCB0b3RhbCBkYXlzLiBEYXNobGluZXMgaW5kaWNhdGUgdGhlIGNvcnJlc3BvbmRpbmcgcGVyY2VudGlsZS4KCiMjIyMgM2IuICByZW1vdmUgZGF5cyBhdCB0aGUgc2Vuc2l0aXZpdHkgdGhyZXNob2xkCk5leHQsIHdlIGFyZSByZW1vdmluZyB0aGUgZGF5cyB3aXRoIGV4Y2Vzc2l2ZSBkYXRhIG1pc3NpbmduZXNzLiBUaGlzIGlzIG9mIGNvdXJzZSBhbiBhcmJpdHJhcnkgc3RlcC4gVGhlcmVmb3JlIHdlIHdpbGwgY29uZHVjdCBhIHNlbnNpdGl2aXR5IGFuYWx5c2lzIG9mIHRoZSBtaXNzaW5nbmVzcyB0aHJlc2hvbGQgd2Ugc2V0IGJ5IHBlcmZvcm1pbmcgdGhlIGFuYWx5c2lzIGFjcm9zcyBtdWx0aXBsZSBkaWZmZXJlbnQgdGhyZXNob2xkcy4gRm9yIG5vdywgdGhlIGN1cnJlbnQgc2Vuc2l0aXZpdHkgY3V0b2ZmIGlzIHNldCBhdCBgciBzZW5zaXRpdml0eV9jdXRvZmZgLCB3aGljaCBhbW91bnRzIHRvIG9ubHkgZXhjbHVkaW5nIHRob3NlIHdpdGggYHIgc2Vuc2l0aXZpdHlfY3V0b2ZmLzE0NDAqMTAwYCUgb2YgR1BTIG1pc3NpbmcuCgpgYGB7ciByZXN1bHRzPSdhc2lzJ30Kc2Vuc2l0aXZpdHlfY3V0b2ZmID0gMTQ0MCAjIHRoaXMgY29udHJvbHMgdGhlIGN1dG9mZiB0aHJlc2hvbGQKZ3BzX2RmX2NsZWFuMiA9IHN1YnNldChncHNfZGZfY2xlYW4sIE1pbnNNaXNzaW5nIDwgc2Vuc2l0aXZpdHlfY3V0b2ZmKQpgYGAKClRoaXMgc3RlcCByZW1vdmVkIGByIGRpbShncHNfZGZfY2xlYW4pWzFdIC0gZGltKGdwc19kZl9jbGVhbjIpWzFdYCBkYXlzLiBOb3csIGRhdGFzZXQgaGFzIGByIGxlbmd0aCh1bmlxdWUoZ3BzX2RmX2NsZWFuMiRJSUQpKWAgc3ViamVjdHMsIGNvbnNpc3Rpbmcgb2YgYHIgZGltKGdwc19kZl9jbGVhbjIpWzFdYCB0b3RhbCBkYXlzLCBhbmQgYHIgbGVuZ3RoKGNvbG5hbWVzKGdwc19kZl9jbGVhbjIpKS0yYCBHUFMgZmVhdHVyZXMuCgpgYGB7ciBmaWcud2lkdGg9MTAsIGZpZy5oZWlnaHQ9NCwgZWNobz1GQUxTRX0KcCA9IG1pbk1pc3NfaGlzdHBsb3QoZ3BzX2RmX2NsZWFuMiwyMDAsIHBhc3RlKCJBZnRlciBSZW1vdmluZyBNaXNzaW5nIEdyZWF0ZXIgdGhhbiAiLHNlbnNpdGl2aXR5X2N1dG9mZikpCmdncGxvdGx5KHApCmBgYAoqKkZpZ3VyZSA0OiBNaW51dGVzIG1pc3NpbmcgYWZ0ZXIgcmVtb3ZpbmcgZGF5cyB3aXRoIGFsbCBkYXRhIG1pc3NpbmcuKiogVGhlcmUgYXJlIGByIGRpbShncHNfZGZfY2xlYW4yKVsxXWAgdG90YWwgZGF5cy4gRGFzaGxpbmVzIGluZGljYXRlIHRoZSBjb3JyZXNwb25kaW5nIHBlcmNlbnRpbGUuCgoKYGBge3IgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTQsIGVjaG89RkFMU0V9CnAgPSBtaW5NaXNzX2hpc3RwbG90KHN1YnNldChncHNfZGZfY2xlYW4yLE1pbnNNaXNzaW5nPj0xMjk2KSwyMDAsICJab29tIEluIFBsb3QiKQpnZ3Bsb3RseShwKQpgYGAKKipGaWd1cmUgNTogQSBab29tLWluIHBsb3Qgb2YgbWludXRlcyBtaXNzaW5nIGRpc3RyaWJ1dGlvbiBhZnRlciByZW1vdmluZyBkYXlzIHdpdGggYWxsIGRhdGEgbWlzc2luZy4qKiBUaGVyZSBhcmUgYHIgZGltKGdwc19kZl9jbGVhbjIpWzFdYCB0b3RhbCBkYXlzLiBEYXNobGluZXMgaW5kaWNhdGUgdGhlIGNvcnJlc3BvbmRpbmcgcGVyY2VudGlsZS4KCiMjIyA0LiBSYW5kb20gRGF0YSBQYXJ0aXRpb25zCgpUbyBvcGVyYXRpb25hbGl6ZSBpbmRpdmlkdWFsIGZvb3RwcmludGluZyBwcmVkaWN0aW9uLCB3ZSByYW5kb21seSBzcGxpdCBlYWNoIGluZGl2aWR1YWwncyBhdmFpbGFibGUgR1BTIGRhdGEgdG8gdHdvIGhhbGYgcGFydGl0aW9ucyBmb3IgYHIgcGFydF90aW1lc2AgdGltZXMuIFdlIHVzZWQgdGhlIGZlYXR1cmVzIGZyb20gdGhlIGZpcnN0IGhhbGYgdG8gZGV0ZXJtaW5lIGlmIHdlIGNhbiBpZGVudGlmeSB0aGUgc2FtZSBpbmRpdmlkdWFsIHVzaW5nIHRoZWlyIGRhdGEgaW4gdGhlIHNlY29uZCB1bnNlZW4gaGFsZi4gQWdhaW4sIHRvIGF2b2lkIGFueSAodW4pbHVja3kgcmFuZG9tIHNwbGl0cywgd2UgcmVwZWF0ZWQgZGF0YSBwYXJ0aXRpb24gYHIgcGFydF90aW1lc2AgdGltZXMuCgpgYGB7cn0Kc2V0LnNlZWQoNTEwKQptYWtlX3N1Ympfc2VxID0gZnVuY3Rpb24oZ3BzX2RmX2NsZWFuMixwYXJ0X3RpbWVzID0gMTApIHsKICBzdWJqX3NlcSA9IGxpc3QoKQogIGZvciAoc3ViaiBpbiB1bmlxdWUoZ3BzX2RmX2NsZWFuMiRJSUQpKXsKICAgIHN1YmpfZGF0YSA9IHN1YnNldChncHNfZGZfY2xlYW4yLCBJSUQ9PXN1YmopCiAgICBzdWJqX3NlcVtbc3Vial1dIDwtY3JlYXRlRGF0YVBhcnRpdGlvbihzdWJqX2RhdGEkSUlELHRpbWVzID0gcGFydF90aW1lcywgcCA9MC41KQogIH0KICByZXR1cm4oc3Vial9zZXEpCn0Kc3Vial9zZXEgPSBtYWtlX3N1Ympfc2VxKGdwc19kZl9jbGVhbjIsIDEwMCkKCmBgYAoKCgojIyMgNS4gQnVpbGQgQ29ycmVsYXRpb24gTWF0cml4CgpIZXJlLCBzaW1pbGFyIHRvIFtGaW5uIGV0IGFsLiBOYXQgTmV1cm8gICgyMDE1KV0oaHR0cHM6Ly93d3cubmF0dXJlLmNvbS9hcnRpY2xlcy9ubi40MTM1KSBhbmQgW0thdWZtYW5uIGV0IGFsLiBOYXQgTmV1cm8gKDIwMTUpXShodHRwczovL3d3dy5uYXR1cmUuY29tL2FydGljbGVzL3M0MTU5My0wMTktMDQ3MS03KSwgd2UgYnVpbHQgYSBQZWFyc29uIGNvcnJlbGF0aW9uIG1hdHJpeCBhbW9uZyBgciBsZW5ndGgoY29sbmFtZXMoZ3BzX2RmX2NsZWFuMikpLTJgIGF2YWlsYWJsZSBHUFMgZmVhdHVyZXMuIEJlbG93IGlzIGFuIGlsbHVzdHJhdGl2ZSBzYW1wbGUgb2YgdGhlIHZhcmlhYmxlcyBhbmQgdGhlaXIgY29ycmVsYXRpb25zLgoKYGBge3IgZXhhbXBsZV9jb3JfZmlnLCBmaWcud2lkdGg9MywgZmlnLndpZHRoPTMsIGZpZy5hbGlnbj0iY2VudGVyIn0KIyBhbiBleGFtcGxlIG9mIHN1YmogMSwgYW5kIGZpcnN0IGhhbGYKZXhhbXBsZV9kYXRhID0gZ3BzX2RmX2NsZWFuMltzdWJqX3NlcSRgMTR3NXFsbzhgJFJlc2FtcGxlMDAxLDM6MTddCmdwc19jb3IgPSBycXVlcnkuY29ybWF0KGV4YW1wbGVfZGF0YSwgdHlwZSA9ICJmdWxsIikKCmBgYAoqKkZpZ3VyZSA2OiBDb3JyZWxhdGlvbiBtYXRyaXggb2YgR1BTIGZlYXR1cmVzIGZvciBhIHN1YmplY3QuKioKCgpXZSB0aGVuIGNhbGN1bGF0ZWQgdGhlIGZlYXR1cmUgbWF0cml4IGZvciBhbGwgYHIgbGVuZ3RoKHVuaXF1ZShncHNfZGZfY2xlYW4yJElJRCkpYCBzdWJqZWN0cyBpbiB0aGUgZGF0YXNldCwgc2VwZXJhdGVseSBmb3IgZWFjaCBoYWxmIGRhdGEgcGFydGl0aW9uLCBhbmQgZm9yIGVhY2ggcmFuZG9tIHNwbGl0LiAKCmBgYHtyIGNyZWF0ZSBmZWF0dXJlIG1hdHJpeCBmb3IgZXZlcnlvbmUsIHdhcm5pbmc9RkFMU0V9Cm1ha2VfZmVhdHVyZV9tYXRyaXggPSBmdW5jdGlvbihncHNfZGYsIHN1Ympfc2VxKSB7CiAgc3Vial9tYXRfMSA9IGxpc3QoKQogIHN1YmpfbWF0XzIgPSBsaXN0KCkKICBmb3IgKHN1YmogaW4gdW5pcXVlKGdwc19kZiRJSUQpKXsKICAgIHN1YmpfZGF0YSA9IHN1YnNldChncHNfZGZfY2xlYW4yLCBJSUQ9PXN1YmopCiAgICBzdWJqX21hdF8xW1tzdWJqXV0gPSBsYXBwbHkoc3Vial9zZXFbW3N1YmpdXSwgZnVuY3Rpb24obGlzdCkgcnF1ZXJ5LmNvcm1hdChzdWJqX2RhdGFbbGlzdCwzOjE3XSwgdHlwZSA9ICJmbGF0dGVuIiwgZ3JhcGggPSBGKSRyKQogICAgc3Vial9tYXRfMltbc3Vial1dID0gbGFwcGx5KHN1Ympfc2VxW1tzdWJqXV0sIGZ1bmN0aW9uKGxpc3QpIHJxdWVyeS5jb3JtYXQoc3Vial9kYXRhWy1saXN0LDM6MTddLCB0eXBlID0gImZsYXR0ZW4iLCBncmFwaCA9IEYpJHIpCiAgfQogIHJldHVybihsaXN0KHN1YmpfbWF0XzEgPSBzdWJqX21hdF8xLCBzdWJqX21hdF8yID0gc3Vial9tYXRfMiApKQp9CgpncHNfY2xlYW4yX2ZlYXR1cmUgPSBtYWtlX2ZlYXR1cmVfbWF0cml4KGdwc19kZl9jbGVhbjIpCmBgYAoKIyMjIDYuIE1hdGNoIFRhcmdldAoKTmV4dCB3ZSB0cmllZCB0byBtYXRjaCBlYWNoIHRhcmdldCwgZGVmaW5lZCBieSBvbmUgc3ViamVjdCdzIGZlYXR1cmUgbWF0cml4IGluIHRoZSBmaXJzdCBoYWxmLCB0byBhIGZlYXR1cmUgbWF0cml4IGluIHRoZSBzZWNvbmQgaGFsZiBpbiB0aGUgc2FtZSByYW5kb20gc3BsaXQuIElmIHRoZSBzYW1lIGluZGl2aWR1YWwncyBmZWF0dXJlIG1hdHJpeCBpbiB0aGUgc2Vjb25kIGhhbGYgaGFkIHRoZSBoaWdoZXN0IGNvcnJlbGF0aW9uIGFtb25nIGFsbCBzdWJqZWN0cywgdGhlbiB3ZSBhc3NpZ25lZCB0aGUgbWF0Y2ggcmVzdWx0IDEsIGluZGljYXRpbmcgYSBzdWNjdXNzZnVsIG1hdGNoLCBvdGhlcndpc2UgMCwgaW5kaWNhdGluZyBhbiB1bnNjY3Vzc2Z1bCBtYXRjaC4KCmBgYHtyIGNhbGMgbWF0Y2ggY29yfQojIGNyZWF0aW5nIGEgImRhdGFiYXNlIiBhZ2FpbnN0IHdoaWNoIHRhcmdldCBpcyB0byBiZSBtYXRjaGVkIHdpdGgKc3Vial9tYXRfMSA9IGdwc19jbGVhbjJfZmVhdHVyZSRzdWJqX21hdF8xCnN1YmpfbWF0XzIgPSBncHNfY2xlYW4yX2ZlYXR1cmUkc3Vial9tYXRfMgoKY2FsY19tYXRjaF9jb3IgPSBmdW5jdGlvbihzdWJqX21hdF8xLHN1YmpfbWF0XzIpIHsKICBwYXJ0X3RpbWVzID0gbGVuZ3RoKHN1YmpfbWF0XzFbWzFdXSkKICBkYXRhYmFzZSA9IGxpc3QoKSAKICBmb3IgKHRpbWUgaW4gMTpwYXJ0X3RpbWVzKSB7CiAgICAgIGRhdGFiYXNlW1t0aW1lXV0gPSBsYXBwbHkoc3Vial9tYXRfMiwgZnVuY3Rpb24oc3Viam1hdCkgc3Viam1hdFtbdGltZV1dJGNvcikKICB9CiAgCiAgICAjIG1hdGNoIHRhcmdldCB0byBkYXRhYmFzZQogICAgbWF0Y2hfY29yID0gbGlzdCgpCiAgICBmb3IgKHN1YmoxIGluIG5hbWVzKHN1YmpfbWF0XzEpKXsgI2xvb3AgdGhyb3VnaCBlYWNoIHN1YmoKICAgICAgIyBjcmVhdGUgYSBsaXN0IG9mIHRhcmdldCBhY3Jvc3MgcGFydGl0aW9ucwogICAgICB0YXJnZXRfbGlzdCA9IGxhcHBseShzdWJqX21hdF8xW1tzdWJqMV1dLCBmdW5jdGlvbihwYXJ0KSBwYXJ0JGNvcikKICAgICAgIyBjcmVhdGUgYSBtYXRjaCBsaXN0CiAgICAgIGZvciAodGltZSBpbiAxOnBhcnRfdGltZXMpewogICAgICAgIHRhcmdldF9zdWJqX3RpbWUgPSB0YXJnZXRfbGlzdFtbdGltZV1dICNsb29wIHRocm91Z2ggZWFjaCBwYXJ0aXRpb24KICAgICAgICBmb3IgKHN1YmoyIGluIG5hbWVzKHN1YmpfbWF0XzIpKXsgI2xvb3AgZXZlcnlvbmUgaW4gMm5kIGhhbGYKICAgICAgICAgIGRhdGFfc3Vial90aW1lID0gc3Vial9tYXRfMltbc3ViajJdXVtbdGltZV1dJGNvcgogICAgICAgICAgbWF0Y2hfY29yW1tzdWJqMV1dW1thcy5jaGFyYWN0ZXIodGltZSldXVtbc3ViajJdXSA9IGNvcih0YXJnZXRfc3Vial90aW1lLGRhdGFfc3Vial90aW1lLHVzZSA9ICJuYS5vci5jb21wbGV0ZSIpCiAgICAgICAgfQogICAgICB9CiAgICB9CiAgcmV0dXJuKG1hdGNoX2NvcikKfQoKbWF0Y2hfY29yID0gY2FsY19tYXRjaF9jb3Ioc3Vial9tYXRfMSxzdWJqX21hdF8yKQoKYGBgCgoKQnkgdGFsbHlpbmcgdXAgYWxsIHRoZSBzdWNjZXNzZnVsIGFuZCB1bnN1Y2Nlc3NmdWwgbWF0Y2hzIGluIGVhY2ggb2YgdGhlIGByIHBhcnRfdGltZXNgIHJhbmRvbSBzcGxpdHMsIHdlIGNhbGN1bGF0ZWQgYSBkaXN0cmlidXRpb24gb2YgbWF0Y2ggYWNjdXJhY3kuCgpgYGB7ciBjYWxjIGFjY3VyYWN5IGJ5IHBhcnRpdGlvbn0KY2FsY19hY2NfdGltZT1mdW5jdGlvbihtYXRjaF9jb3IscGFydF90aW1lcykgewogIGFjY190aW1lID0gYXJyYXkoKQogIGZvciAodGltZSBpbiAxOnBhcnRfdGltZXMpewogICAgYWNjX3RpbWVbdGltZV0gPSAwCiAgICBmb3IgKHN1YmogaW4gbmFtZXMoc3Vial9tYXRfMSkpewogICAgICBtYXhfcG9zaXRpb24gPSB3aGljaC5tYXgodW5saXN0KG1hdGNoX2Nvcltbc3Vial1dW1thcy5jaGFyYWN0ZXIodGltZSldXSkpCiAgICAgIHByZWRpY3RlZF9zdWJqID0gbmFtZXMoc3Vial9tYXRfMSlbbWF4X3Bvc2l0aW9uXQogICAgICBpZiAocHJlZGljdGVkX3N1YmogPT0gc3ViaikgewogICAgICAgIGFjY190aW1lW3RpbWVdID0gYWNjX3RpbWVbdGltZV0gKyAxCiAgICAgIH0KICAgIH0KICB9CiAgYWNjX3RpbWUgPSBhY2NfdGltZS9sZW5ndGgobmFtZXMoc3Vial9tYXRfMSkpCiAgcmV0dXJuKGFjY190aW1lKQp9CmFjY190aW1lID0gY2FsY19hY2NfdGltZShtYXRjaF9jb3IscGFydF90aW1lcykKYGBgCgpPdmVyIHRoZSBgciBwYXJ0X3RpbWVzYCByYW5kb20gc3BsaXRzLCB0aGUgbWVhbiBtYXRjaCBhY2N1cmFjeSB3YXMgYHIgcm91bmQobWVhbihhY2NfdGltZSksNCkqMTAwYCUsIHdpdGggYSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYHIgcm91bmQoc2QoYWNjX3RpbWUpLDQpKjEwMGAlLCBoaWdoIG9mIGByIHJvdW5kKG1heChhY2NfdGltZSksNCkqMTAwYCUsIGFuZCBsb3cgb2YgYHIgcm91bmQobWluKGFjY190aW1lKSw0KSoxMDBgJSwgKDk1JUNJOiBgciByb3VuZChDSShhY2NfdGltZSlbJ2xvd2VyJ10sMilgLWByIHJvdW5kKENJKGFjY190aW1lKVsndXBwZXInXSwyKWApLgoKYGBge3IgcGxvdCBhY2N1cmFjeSBieSBwYXJ0aXRpb24gaGlzdG9ncmFtLCBmaWcud2lkdGg9OCwgZmlnLmhlaWdodD00fQpwX3RpbWVfY29yID0gaGlzdF9jaHgoYWNjX3RpbWUsIGJpbnMgPSAxNSwgdGl0bGUgPSBwYXN0ZSgiQ29ycmVsYXRlZCBGZWF0dXJlczogXG4gQXZlcmFnZSBBY2N1cmFjeSBBY3Jvc3MiLHBhcnRfdGltZXMsIkRhdGEgUGFydGl0aW9ucyIpLCB4YXhpcyA9ICJQcmVkaWN0aW9uIEFjY3VyYWN5IiwgeWF4aXMgPSAiQ291bnQiKQpnZ3Bsb3RseShwX3RpbWVfY29yKQpgYGAKKipGaWd1cmUgNzogTWF0Y2ggYWNjdXJhY3kgZGlzdHJpYnV0b24gYWNyb3NzIGByIHBhcnRfdGltZXNgIGRhdGEgc3BsaXRzLioqIE1lYW4gbWF0Y2ggYWNjdXJhY3kgd2FzIGByIHJvdW5kKENJKGFjY190aW1lKVsnbWVhbiddLDIpYCAoOTUlQ0k6IGByIHJvdW5kKENJKGFjY190aW1lKVsnbG93ZXInXSwyKWAtYHIgcm91bmQoQ0koYWNjX3RpbWUpWyd1cHBlciddLDIpYCkKCgpgYGB7ciBjYWxjIGFjY3VyYWN5IGJ5IHN1Ymp9CmNhbGNfYWNjX3N1YmogPSBmdW5jdGlvbihtYXRjaF9jb3IsIHBhcnRfdGltZXMpewogIGFjY19zdWJqID0gYXJyYXkoKQogIGZvciAoc3ViaiBpbiBuYW1lcyhzdWJqX21hdF8xKSl7CiAgICBhY2Nfc3VialtzdWJqXSA9IDAKICAgIGZvciAodGltZSBpbiAxOnBhcnRfdGltZXMpewogICAgICBtYXhfcG9zaXRpb24gPSB3aGljaC5tYXgodW5saXN0KG1hdGNoX2Nvcltbc3Vial1dW1thcy5jaGFyYWN0ZXIodGltZSldXSkpCiAgICAgIHByZWRpY3RlZF9zdWJqID0gbmFtZXMoc3Vial9tYXRfMSlbbWF4X3Bvc2l0aW9uXQogICAgICBpZiAocHJlZGljdGVkX3N1YmogPT0gc3ViaikgewogICAgICAgIGFjY19zdWJqW3N1YmpdID0gYWNjX3N1Ympbc3Vial0gKyAxCiAgICAgIH0KICAgIH0KICB9CiAgYWNjX3N1YmogPSBhY2Nfc3Viai9wYXJ0X3RpbWVzCiAgYWNjX3N1YmogPSBhY2Nfc3VialstMV0KICByZXR1cm4oYWNjX3N1YmopCn0KYWNjX3N1YmogPSBjYWxjX2FjY19zdWJqKG1hdGNoX2NvciwgcGFydF90aW1lcykKYGBgCgoKSW4gYWRkaXRpb24gdG8gdGhlIG1hdGNoIGFjY3VyYWN5IGFjcm9zcyBzdWJqZWN0cywgd2UgYWxzbyBjYWxjdWxhdGVkIHRoZSBtYXRjaCBhY2N1cmFjeSBmb3IgZWFjaCBpbmRpdmlkdWFsLiBBY3Jvc3MgdGhlIGByIGxlbmd0aCh1bmlxdWUoZ3BzX2RmX2NsZWFuMiRJSUQpKWAgc3ViamVjdHMsIHRoZSBtZWFuIG1hdGNoIGFjY3VyYWN5IHdhcyBgciByb3VuZChtZWFuKHN1YmpfZGYkeSksNCkqMTAwYCUsIHdpdGggYSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYHIgcm91bmQoc2Qoc3Vial9kZiR5KSw0KSoxMDBgJSwgaGlnaCBvZiBgciByb3VuZChtYXgoc3Vial9kZiR5KSw0KSoxMDBgJSwgYW5kIGxvdyBvZiBgciByb3VuZChtaW4oc3Vial9kZiR5KSw0KSoxMDBgJS4KCmBgYHtyIHBsb3QgYWNjdXJhY3kgYnkgc3ViamVjdHMsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTR9CnN1Ympfc2NhdHRlciAgPSBmdW5jdGlvbihncHNfZGYsIGFjY19zdWJqX3ZlY3RvciwgbWV0aG9kKXsKICBzdWJqX2RmIDwtIGRhdGEuZnJhbWUoeD11bmlxdWUoZ3BzX2RmJElJRCkpCiAgc3Vial9kZiR5ID0gYWNjX3N1YmpfdmVjdG9yCiAgc3Vial9kZiA9IHN1YmpfZGZbb3JkZXIoc3Vial9kZiR5KSxdCiAgc3Vial9hY2NfcGxvdCA9IGdncGxvdChzdWJqX2RmKSArIAogIGdlb21fcG9pbnQoYWVzKHggPSByZW9yZGVyKHgsIHkpLCB5ID0geSkpICsgCiAgIHRoZW1lX2Nvd3Bsb3QoKSArIAogICAgbGFicyh0aXRsZSA9IHBhc3RlKG1ldGhvZCwiRmVhdHVyZXMgXG4gU3ViamVjdCBMZXZlbCBBY2N1cmFjeSBBY3Jvc3MiLHBhcnRfdGltZXMsIkRhdGEgUGFydGl0aW9ucyIpLCAKICAgICAgIHggPSAiU3ViamVjdHMiLCB5ID0gIlByZWRpY3Rpb24gQWNjdXJhY3kiKSArCiAgIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gNDUsIGhqdXN0ID0gMSwgc2l6ZSA9IDgpLCBwbG90LnRpdGxlID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMC41KSkKICByZXR1cm4oc3Vial9hY2NfcGxvdCkKfQoKZ2dwbG90bHkoc3Vial9zY2F0dGVyKGdwc19kZl9jbGVhbjIsYWNjX3N1YmosICJDb3JyZWxhdGVkIikpCmBgYAoqKkZpZ3VyZSA4OiBNYXRjaCBhY2N1cmFjeSBkaXN0cmlidXRvbiBhY3Jvc3MgYHIgbGVuZ3RoKHVuaXF1ZShncHNfZGZfY2xlYW4yJElJRCkpYCBzdWJqZWN0cy4qKiBNZWFuIG1hdGNoIGFjY3VyYWN5IHdhcyBgciByb3VuZChtZWFuKHN1YmpfZGYkeSksNCkqMTAwYCUsIHdpdGggYSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYHIgcm91bmQoc2Qoc3Vial9kZiR5KSw0KSoxMDBgJSwgaGlnaCBvZiBgciByb3VuZChtYXgoc3Vial9kZiR5KSw0KSoxMDBgJSwgYW5kIGxvdyBvZiBgciByb3VuZChtaW4oc3Vial9kZiR5KSw0KSoxMDBgJS4gVGhpcyBzaG93cyBkcmFtYXRpYyBkaWZmZXJlbmNlcyBpbiBpbmRpdmlkdWFsICpmb290cHJpbnRpbmcgZGlzdGluY3RpdmVuZXNzKi4KCgojIyMgNy4gUGVybXV0YXRpb24gVGVzdAoKVG8gYXNzZXNzIHRoZSBzdGF0aXN0aWNhbCBzaWduaWZpY2FuY2Ugb2YgdGhlIHJlc3VsdHMgYWJvdmUsIHdlIGNvbmR1Y3RlZCBhIG5vbi1wYXJhbWV0cmljIHBlcm11dGF0aW9uIHRlc3QuIFRvIGRvIHRoaXMsIHdlIHJhbmRvbWx5IHNjcmFtYmxlZCBwYWlyLXdpc2Ugc3ViamVjdC10by1kYXkgbGlua2FnZS4gV2UgcmVwZWF0ZWQgdGhpcyBwcm9jZXNzIGByIHBlcm1fdGltZWAgdGltZXMsIGFuZCBmb2xsb3dlZCB0aGUgc2FtZSBwcm9jZWR1cmUgYXMgYWJvdmUgdG8gb2J0YWluIGEgbnVsbCBkaXN0cmlidXRpb24gb2YgYXZlcmFnZSBtYXRjaCBhY2N1cmFjeSBhY3Jvc3Mgc2FtcGxlLCBhbmQgZm9yIGVhY2ggaW5kaXZpZHVhbC4KCmBgYHtyIGNhbGMgcGVybXV0YXRpb24gYWNjdXJhY3ksIGVjaG89VFJVRSwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KZ3BzX2RmX3Blcm0gPSBncHNfZGZfY2xlYW4yCnBlcm1fdGltZSA9IDEwMDAKcGVybV9hY2NfdGltZSA9IGxpc3QoKQpwZXJtX2FjY19zdWJqID0gbGlzdCgpCmZvciAoaSBpbiAxOnBlcm1fdGltZSkgewogIHBlcm1fcGFydF90aW1lcyA9IDEKICBwcmludChwYXN0ZSgicHJvY2Vzc2luZyAuLi4iLCBpLCIuLi4iKSkKICBncHNfZGZfcGVybSRJSUQgPSBzYW1wbGUoZ3BzX2RmX3Blcm0kSUlEKQogIHBlcm1fc3Vial9zZXEgPSBtYWtlX3N1Ympfc2VxKGdwc19kZl9wZXJtLHBhcnRfdGltZXMgPSBwZXJtX3BhcnRfdGltZXMpCiAgcGVybV9ncHMgPSBtYWtlX2ZlYXR1cmVfbWF0cml4KGdwc19kZl9wZXJtLHBlcm1fc3Vial9zZXEpCiAgcGVybV9tYXRfMSA9IHBlcm1fZ3BzJHN1YmpfbWF0XzEKICBwZXJtX21hdF8yID0gcGVybV9ncHMkc3Vial9tYXRfMgogIHBlcm1fbWF0Y2hfY29yID0gY2FsY19tYXRjaF9jb3IocGVybV9tYXRfMSxwZXJtX21hdF8yKQogIHBlcm1fYWNjX3RpbWVbW2ldXSA9IGNhbGNfYWNjX3RpbWUocGVybV9tYXRjaF9jb3IscGFydF90aW1lcyA9IHBlcm1fcGFydF90aW1lcykKICBwZXJtX2FjY19zdWJqW1tpXV0gPSBjYWxjX2FjY19zdWJqKHBlcm1fbWF0Y2hfY29yLHBhcnRfdGltZXMgPSBwZXJtX3BhcnRfdGltZXMpCn0KYGBgCgoKT3ZlciB0aGUgYHIgcGVybV90aW1lYCBwZXJtdXRhdGlvbnMsIHRoZSBtZWFuIG1hdGNoIGFjY3VyYWN5IHdhcyBgciByb3VuZChtZWFuKHBlcm1fYWNjX3RpbWVfYWxsKSw0KSoxMDBgJSwgd2l0aCBhIHN0YW5kYXJkIGRldmlhdGlvbiBvZiBgciByb3VuZChzZChwZXJtX2FjY190aW1lX2FsbCksNCkqMTAwYCUsIGhpZ2ggb2YgYHIgbWF4KG1lYW4ocGVybV9hY2NfdGltZV9hbGwpLDQpKjEwMGAlLCBhbmQgbG93IG9mIGByIG1pbihtZWFuKHBlcm1fYWNjX3RpbWVfYWxsKSw0KSoxMDBgJS4oOTUlQ0k6IGByIHJvdW5kKENJKHBlcm1fYWNjX3RpbWVfYWxsKVsnbG93ZXInXSwyKWAtYHIgcm91bmQoQ0kocGVybV9hY2NfdGltZV9hbGwpWyd1cHBlciddLDIpYCkKCmBgYHtyIGNvbWJpbmUgcGFydGl0aW9uIHBlcm11dGF0aW9uIHJlc3VsdHMsIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTR9CnBlcm1fYWNjX3RpbWVfYWxsID0gdW5saXN0KHBlcm1fYWNjX3RpbWUpCnFfdGltZV9jb3IgPSBoaXN0X2NoeChwZXJtX2FjY190aW1lX2FsbCwgYmlucyA9IDgsIHRpdGxlID0gcGFzdGUoIkF2ZXJhZ2UgQWNjdXJhY3kgQWNyb3NzIixsZW5ndGgocGVybV9hY2NfdGltZV9hbGwpLCJQZXJtdXRhdGlvbnMiKSwgeGF4aXMgPSAiUHJlZGljdGlvbiBBY2N1cmFjeSIsIHlheGlzID0gIkNvdW50IikKZ2dwbG90bHkocV90aW1lX2NvcikKYGBgCioqRmlndXJlIDk6IE1hdGNoIGFjY3VyYWN5IGRpc3RyaWJ1dG9uIGFjcm9zcyBgciBwZXJtX3RpbWVgIHBlcm11dGF0aW9ucy4qKiBNZWFuIG1hdGNoIGFjY3VyYWN5IGluIHBlcm11dGF0aW9uIHdhcyBgciByb3VuZChDSShwZXJtX2FjY190aW1lX2FsbClbJ21lYW4nXSwyKWAgKDk1JUNJOiBgciByb3VuZChDSShwZXJtX2FjY190aW1lX2FsbClbJ2xvd2VyJ10sMilgLWByIHJvdW5kKENJKHBlcm1fYWNjX3RpbWVfYWxsKVsndXBwZXInXSwyKWApLiBUaGlzIG51bGwgZGlzdHJpYnV0aW9uIGRvZXMgbm90IG92ZXJsYXBwIHdpdGggdGhlIGRpc3RyaWJ1dG9uIHVzaW5nIHJlYWwgZGF0YSAoKipGaWcuNyoqKSBhdCBhbGwuCgoKV2UgYWxzbyBjYWxjdWxhdGVkIG51bGwgZGlzdHJpYnV0aW9uIG9mIG1hdGNoIGFjY3VyYWN5IGZvciBlYWNoIHN1YmplY3QuIE92ZXIgdGhlIGByIHBlcm1fdGltZWAgcGVybXV0YXRpb25zLCB0aGUgbWVhbiBtYXRjaCBhY2N1cmFjeSB3YXMgYHIgcm91bmQobWVhbihzdWJqX2RmJHlfcGVybSksNCkqMTAwYCUsIHdpdGggYSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYHIgcm91bmQoc2Qoc3Vial9kZiR5X3Blcm0pLDQpKjEwMGAlLCBoaWdoIG9mIGByIHJvdW5kKG1heChzdWJqX2RmJHlfcGVybSksNCkqMTAwYCUsIGFuZCBsb3cgb2YgYHIgcm91bmQobWluKHN1YmpfZGYkeV9wZXJtKSw0KSoxMDBgJS4KCmBgYHtyIGNvbWJpbmUgc3ViaiBwZXJtdXRhdGlvbiBhbmFseXNpc30KcGVybV9zdWJqID0gbGlzdCgpCmZvciAoc3ViaiBpbiBzdWJqX2FjY19wbG90JGRhdGEkeCkgewogIHBlcm1fc3ViaiR2YWxbW3N1YmpdXSA9IHNhcHBseShwZXJtX2FjY19zdWJqLCBmdW5jdGlvbihwZXJtKSBwZXJtW3doaWNoKG5hbWVzKHBlcm0pID09IHN1YmopXSkKICBwZXJtX3N1YmokaGlzdFtbc3Vial1dID0gaGlzdF9jaHgocGVybV9zdWJqW1tzdWJqXV0kdmFsLCBiaW5zID0gOCwgdGl0bGUgPSBwYXN0ZShzdWJqLCI6IEFjY3VyYWN5IEFjcm9zcyBcbiIscGVybV90aW1lLCJQZXJtdXRhdGlvbnMiKSwgeGF4aXMgPSAiUHJlZGljdGlvbiBBY2N1cmFjeSIsIHlheGlzID0gIkNvdW50IikKICBwZXJtX3N1YmokYWNjW1tzdWJqXV0gPSBzdW0ocGVybV9zdWJqJHZhbFtbc3Vial1dKS9wZXJtX3RpbWUKfQpgYGAKCmBgYHtyIHBsb3Qgc3ViaiBhbmFseXNpcyB3aXRoIHBlcm0sIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTR9CnN1YmpfZGYgPC0gZGF0YS5mcmFtZSh4PXVuaXF1ZShncHNfZGZfY2xlYW4yJElJRCkpCnN1YmpfZGYkeSA9IGFjY19zdWJqCnN1YmpfZGYkeV9wZXJtID0gdW5saXN0KHBlcm1fc3ViaiRhY2MpCnN1YmpfZGYgPSBzdWJqX2RmW29yZGVyKHN1YmpfZGYkeSksXQpwX3N1YmpfY29yX3Blcm0gPSBnZ3Bsb3Qoc3Vial9kZiwgYWVzKHggPSByZW9yZGVyKHgsIHkpLCB5ID0gdmFsdWUpKSArIAogIGdlb21fcG9pbnQoYWVzKHkgPSB5LCBjb2wgPSAic3ViamVjdCBkYXRhIikpICsgCiAgZ2VvbV9wb2ludChhZXMoeSA9IHlfcGVybSwgY29sID0gInBlcm11dGF0aW9uIikpICsKICB0aGVtZV9jb3dwbG90KCkgKyAKICBsYWJzKHRpdGxlID0gcGFzdGUoIkNvciBGZWF0dXJlcyBcbiBTdWJqZWN0IExldmVsIEFjY3VyYWN5IEFjcm9zcyIscGFydF90aW1lcywiRGF0YSBQYXJ0aXRpb25zIiksIAogICAgICAgeCA9ICJTdWJqZWN0cyIsIHkgPSAiUHJlZGljdGlvbiBBY2N1cmFjeSIpICsKICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDQ1LCBoanVzdCA9IDEsIHNpemUgPSA4KSwgcGxvdC50aXRsZSA9IGVsZW1lbnRfdGV4dChoanVzdCA9IDAuNSkpCmdncGxvdGx5KHBfc3Vial9jb3JfcGVybSkKYGBgCioqRmlndXJlIDg6IE1hdGNoIGFjY3VyYWN5IG51bGwgZGlzdHJpYnV0b24gYWNyb3NzIGByIGxlbmd0aCh1bmlxdWUoZ3BzX2RmX2NsZWFuMiRJSUQpKWAgc3ViamVjdHMuKiogTWVhbiBtYXRjaCBhY2N1cmFjeSBpbiBwZXJtdXRhdGlvbiB3YXMgYHIgcm91bmQobWVhbihzdWJqX2RmJHlfcGVybSksNCkqMTAwYCUsIHdpdGggYSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgYHIgcm91bmQoc2Qoc3Vial9kZiR5X3Blcm0pLDQpKjEwMGAlLCBoaWdoIG9mIGByIHJvdW5kKG1heChzdWJqX2RmJHlfcGVybSksNCkqMTAwYCUsIGFuZCBsb3cgb2YgYHIgcm91bmQobWluKHN1YmpfZGYkeV9wZXJtKSw0KSoxMDBgJS4gV2hpbGUgaW5kaXZpZHVhbHMgZXhoaWJpdGVkIG1hcmtlZCBkaWZmZXJlbmNlcyBpbiBmb290cHJpbnRpbmcgZGlzdGluY3RpdmVuc3MsIHRoZSBzdWJqZWN0IHdpdGggdGhlIGxvd2VzdCBwcmVkaWN0aW9uIGFjY3VyYWN5IHdhcyBzdGlsbCBzdGF0aXN0aWNhbGx5IHNpZ25pZmljYW50IGFnYWluc3QgdGhlIHBlcm11dGF0aW9uIHRlc3QgKGkuZS4gZm9yIHN1YmplY3QgYHIgc3Vial9kZiR4WzFdYDogZGF0YTogYHIgcm91bmQobWluKHN1YmpfZGYkeSksNCkqMTAwYCAlIHZzLiBwZXJtdXRhdGlvbjogYHIgcm91bmQobWluKHN1YmpfZGYkeV9wZXJtKSw0KSoxMDBgJSkuCgoKIyMjIDguIE1lYW4gRmVhdHVyZXMKCldlIGNhbGN1bGF0ZWQgdGhlIGBtZWFuYCBvZiBlYWNoIEdQUyBmZWF0dXJlIGFzIGEgbWV0cmljIG9mIGZlYXR1cmUgdmFyaWFiaWxpdHkuIFNpbWlsYXIgdG8gYWJvdmUsIHdlIGNhbGN1bGF0ZWQgYG1lYW5gIHNlcGFyYXRlbHkgZm9yIGVhY2ggZGF0YSBwYXJ0aXRpb24gYW5kIGZvciBlYWNoIGluZGl2aWR1YWwuCgpgYGB7ciBjYWxjIG1lYW4gR1BTIGZlYXR1cmVzfQptZWFuX2dwcyA9IGZ1bmN0aW9uKGdwc19kZil7CiAgbWVhbl9saXN0ID0gc2FwcGx5KDM6MTcsZnVuY3Rpb24oaSkgbWVhbihncHNfZGZbLGldLG5hLnJtPVQpKQogIG5hbWVzKG1lYW5fbGlzdCkgPSBjb2xuYW1lcyhncHNfZGYpWzM6MTddCiAgcmV0dXJuKG1lYW5fbGlzdCkKfQoKbWFrZV9mZWF0dXJlX21lYW4gPSBmdW5jdGlvbihncHNfZGYsIHN1Ympfc2VxKSB7CiAgc3Vial9tYXRfMSA9IGxpc3QoKQogIHN1YmpfbWF0XzIgPSBsaXN0KCkKICBmb3IgKHN1YmogaW4gdW5pcXVlKGdwc19kZiRJSUQpKXsKICAgIHN1YmpfZGF0YSA9IHN1YnNldChncHNfZGZfY2xlYW4yLCBJSUQ9PXN1YmopCiAgICBzdWJqX21hdF8xW1tzdWJqXV0gPSBsYXBwbHkoc3Vial9zZXFbW3N1YmpdXSwgZnVuY3Rpb24obGlzdCkgbWVhbl9ncHMoc3Vial9kYXRhW2xpc3QsXSkpCiAgICBzdWJqX21hdF8yW1tzdWJqXV0gPSBsYXBwbHkoc3Vial9zZXFbW3N1YmpdXSwgZnVuY3Rpb24obGlzdCkgbWVhbl9ncHMoc3Vial9kYXRhWy1saXN0LF0pKQogIH0KICByZXR1cm4obGlzdChzdWJqX21hdF8xID0gc3Vial9tYXRfMSwgc3Vial9tYXRfMiA9IHN1YmpfbWF0XzIgKSkKfQoKZ3BzX2NsZWFuMl9tZWFuX2ZlYXQgPSBtYWtlX2ZlYXR1cmVfbWVhbihncHNfZGZfY2xlYW4yLCBzdWJqX3NlcSkKYGBgCgpgYGB7ciB3YXJwIG1lYW4gZmVhdHVyZSBsaXN0IHRvIGRhdGEgZnJhbWUsIGZpZy5oZWlnaHQ9NiwgZWNobz1GfQptZWFuX2RmID0gbGlzdCgpCmZvciAoc3ViaiBpbiB1bmlxdWUoZ3BzX2RmJElJRCkpIHsKICBtZWFuX2RmW1tzdWJqXV0gPSBkYXRhLmZyYW1lKG1hdHJpeChOQSwgcGFydF90aW1lcywgbGVuZ3RoKGNvbG5hbWVzKGdwc19kZl9jbGVhbikpLTIpKQogIGZvciAoaSBpbiAxOnBhcnRfdGltZXMpewogICAgbWVhbl9kZltbc3Vial1dW2ksXSA9IGdwc19jbGVhbjJfbWVhbl9mZWF0JHN1YmpfbWF0XzFbW3N1YmpdXVtbaV1dCiAgfQogIGNvbG5hbWVzKG1lYW5fZGZbW3N1YmpdXSkgPSBjb2xuYW1lcyhncHNfZGZfY2xlYW5bMzoxN10pCn0KCm1lYW5fcGxvdHMgPSBsaXN0KCkKZm9yIChncHNfZnQgaW4gY29sbmFtZXMoZ3BzX2RmX2NsZWFuWzM6MTddKSl7CiAgbWVhbl9wbG90c1tbZ3BzX2Z0XV0gPSBoaXN0X2NoeChzYXBwbHkobWVhbl9kZiwgZnVuY3Rpb24oZGYpIGRmWzEsZ3BzX2Z0XSksIHRpdGxlID0gZ3BzX2Z0LCB4YXhpcyA9ICJGZWF0dXJlIE1lYW4iLCB5YXhpcyA9ICJjb3VudCIpCn0KClJlZHVjZShgK2AsIG1lYW5fcGxvdHMpCmBgYAoqKkZpZ3VyZSA5OiBGZWF0dXJlIG1lYW4gYWNyb3NzIGFsbCBzdWJqZWN0cyoqLiBUaGUgaGlzdG9ncmFtIGFyZSBmb3IgZGF0YSBpbiB0aGUgZmlyc3QgcmFuZG9tIGhhbGYgc3BsaXQuCgoKCiMjIyA5LiBWYXJpYWJpbGl0eSBGZWF0dXJlcwpXZSBjYWxjdWxhdGVkIHRoZSBgcm9vdCBtZWFuIHNxdWFyZSBvZiBzdWNjZXNzaXZlIGRpZmZlcmVuY2VzYCBvciBgUk1TU0RgIG9mIGVhY2ggR1BTIGZlYXR1cmUgYXMgYSBtZXRyaWMgb2YgZmVhdHVyZSB2YXJpYWJpbGl0eS4gU2ltaWxhciB0byBhYm92ZSwgd2UgY2FsY3VsYXRlZCBgUk1TU0RgIHNlcGFyYXRlbHkgZm9yIGVhY2ggZGF0YSBwYXJ0aXRpb24gYW5kIGZvciBlYWNoIGluZGl2aWR1YWwuCgpgYGB7ciBjYWxjdWxhdGUgdmFyaWFiaWxpdHkgZmVhdHVyZXN9CnJtc3NkX2dwcyA9IGZ1bmN0aW9uKGdwc19kZil7CiAgcm1zc2RfbGlzdCA9IHNhcHBseSgzOjE3LGZ1bmN0aW9uKGkpIHJtc3NkX2lkKGdwc19kZlssaV0sIGdwc19kZiRJSUQsbG9uZz1GKSkKICBuYW1lcyhybXNzZF9saXN0KSA9IGNvbG5hbWVzKGdwc19kZilbMzoxN10KICByZXR1cm4ocm1zc2RfbGlzdCkKfQoKbWFrZV9mZWF0dXJlX3Jtc3NkID0gZnVuY3Rpb24oZ3BzX2RmLCBzdWJqX3NlcSkgewogIHN1YmpfbWF0XzEgPSBsaXN0KCkKICBzdWJqX21hdF8yID0gbGlzdCgpCiAgZm9yIChzdWJqIGluIHVuaXF1ZShncHNfZGYkSUlEKSl7CiAgICBzdWJqX2RhdGEgPSBzdWJzZXQoZ3BzX2RmX2NsZWFuMiwgSUlEPT1zdWJqKQogICAgc3Vial9tYXRfMVtbc3Vial1dID0gbGFwcGx5KHN1Ympfc2VxW1tzdWJqXV0sIGZ1bmN0aW9uKGxpc3QpIHJtc3NkX2dwcyhzdWJqX2RhdGFbbGlzdCxdKSkKICAgIHN1YmpfbWF0XzJbW3N1YmpdXSA9IGxhcHBseShzdWJqX3NlcVtbc3Vial1dLCBmdW5jdGlvbihsaXN0KSBybXNzZF9ncHMoc3Vial9kYXRhWy1saXN0LF0pKQogIH0KICByZXR1cm4obGlzdChzdWJqX21hdF8xID0gc3Vial9tYXRfMSwgc3Vial9tYXRfMiA9IHN1YmpfbWF0XzIgKSkKfQoKZ3BzX2NsZWFuMl9ybXNzZF9mZWF0ID0gbWFrZV9mZWF0dXJlX3Jtc3NkKGdwc19kZl9jbGVhbjIsIHN1Ympfc2VxKQpgYGAKCmBgYHtyIHdhcnAgdmFyIGZlYXR1cmUgbGlzdCB0byBkYXRhIGZyYW1lLCBmaWcuaGVpZ2h0PTYsIGVjaG89Rn0KdmFyX2RmID0gbGlzdCgpCmZvciAoc3ViaiBpbiB1bmlxdWUoZ3BzX2RmJElJRCkpIHsKICB2YXJfZGZbW3N1YmpdXSA9IGRhdGEuZnJhbWUobWF0cml4KE5BLCBwYXJ0X3RpbWVzLCBsZW5ndGgoY29sbmFtZXMoZ3BzX2RmX2NsZWFuKSktMikpCiAgZm9yIChpIGluIDE6cGFydF90aW1lcyl7CiAgICB2YXJfZGZbW3N1YmpdXVtpLF0gPSBncHNfY2xlYW4yX3Jtc3NkX2ZlYXQkc3Vial9tYXRfMVtbc3Vial1dW1tpXV0KICB9CiAgY29sbmFtZXModmFyX2RmW1tzdWJqXV0pID0gY29sbmFtZXMoZ3BzX2RmX2NsZWFuWzM6MTddKQp9Cgp2YXJfcGxvdHMgPSBsaXN0KCkKZm9yIChncHNfZnQgaW4gY29sbmFtZXMoZ3BzX2RmX2NsZWFuWzM6MTddKSl7CiAgdmFyX3Bsb3RzW1tncHNfZnRdXSA9IGhpc3RfY2h4KHNhcHBseSh2YXJfZGYsIGZ1bmN0aW9uKGRmKSBkZlsxLGdwc19mdF0pLCB0aXRsZSA9IGdwc19mdCwgeGF4aXMgPSAiRmVhdHVyZSBWYXJpYWJpbGl0eShSTVNTRCkiLCB5YXhpcyA9ICJjb3VudCIpCn0KClJlZHVjZShgK2AsIHZhcl9wbG90cykKYGBgCioqRmlndXJlIDEwOiBGZWF0dXJlIHZhcmlhYmlsaXR5IGZvciBhbGwgc3ViamVjdHMqKi4gVmFyaWFiaWxpdHkgaXMgbWVhc3VyZWQgYnkgYHJvb3QgbWVhbiBzcXVhcmUgb2Ygc3VjY2Vzc2l2ZSBkaWZmZXJlbmNlc2AgKFJNU1NEKS4gVGhlIGhpc3RvZ3JhbXMgYXJlIGZvciBkYXRhIGluIHRoZSBmaXJzdCByYW5kb20gaGFsZiBzcGxpdC4KCgoKIyMjIDEwLiBQcmVkaWN0IHdpdGggTmV3IEZlYXR1cmVzIApgYGB7ciBkZWZpbmUgbWF0Y2ggZnVuY3Rpb24gZm9yIHZlY3RvciBmZWF0dXJlc30KY2FsY19tYXRjaF92ZWN0b3IgPSBmdW5jdGlvbihzdWJqX21hdF8xLHN1YmpfbWF0XzIpIHsKICBwYXJ0X3RpbWVzID0gbGVuZ3RoKHN1YmpfbWF0XzFbWzFdXSkKICBkYXRhYmFzZSA9IGxpc3QoKSAKICBmb3IgKHRpbWUgaW4gMTpwYXJ0X3RpbWVzKSB7CiAgICAgIGRhdGFiYXNlW1t0aW1lXV0gPSBsYXBwbHkoc3Vial9tYXRfMiwgZnVuY3Rpb24oc3Viam1hdCkgc3Viam1hdFtbdGltZV1dKQogIH0KICAKICAgICMgbWF0Y2ggdGFyZ2V0IHRvIGRhdGFiYXNlCiAgICBtYXRjaF9jb3IgPSBsaXN0KCkKICAgIGZvciAoc3ViajEgaW4gbmFtZXMoc3Vial9tYXRfMSkpeyAjbG9vcCB0aHJvdWdoIGVhY2ggc3ViagogICAgICAjIGNyZWF0ZSBhIGxpc3Qgb2YgdGFyZ2V0IGFjcm9zcyBwYXJ0aXRpb25zCiAgICAgIHRhcmdldF9saXN0ID0gbGFwcGx5KHN1YmpfbWF0XzFbW3N1YmoxXV0sIGZ1bmN0aW9uKHBhcnQpIHBhcnQpCiAgICAgICMgY3JlYXRlIGEgbWF0Y2ggbGlzdAogICAgICBmb3IgKHRpbWUgaW4gMTpwYXJ0X3RpbWVzKXsKICAgICAgICB0YXJnZXRfc3Vial90aW1lID0gdGFyZ2V0X2xpc3RbW3RpbWVdXSAjbG9vcCB0aHJvdWdoIGVhY2ggcGFydGl0aW9uCiAgICAgICAgZm9yIChzdWJqMiBpbiBuYW1lcyhzdWJqX21hdF8yKSl7ICNsb29wIGV2ZXJ5b25lIGluIDJuZCBoYWxmCiAgICAgICAgICBkYXRhX3N1YmpfdGltZSA9IHN1YmpfbWF0XzJbW3N1YmoyXV1bW3RpbWVdXQogICAgICAgICAgbWF0Y2hfY29yW1tzdWJqMV1dW1thcy5jaGFyYWN0ZXIodGltZSldXVtbc3ViajJdXSA9IGNvcih0YXJnZXRfc3Vial90aW1lLGRhdGFfc3Vial90aW1lLHVzZSA9ICJuYS5vci5jb21wbGV0ZSIpCiAgICAgICAgfQogICAgICB9CiAgICB9CiAgcmV0dXJuKG1hdGNoX2NvcikKfQpgYGAKCgpgYGB7ciBjYWxjIG1hdGNoIGFjY3VyYWN5IHVzaW5nIG1lYW4gZmVhdHVyZXN9Cm1hdGNoX21lYW4gPSBjYWxjX21hdGNoX3ZlY3RvcihncHNfY2xlYW4yX21lYW5fZmVhdCRzdWJqX21hdF8xLGdwc19jbGVhbjJfbWVhbl9mZWF0JHN1YmpfbWF0XzIpCmFjY190aW1lX21lYW4gPSBjYWxjX2FjY190aW1lKG1hdGNoX21lYW4scGFydF90aW1lcykKYWNjX3N1YmpfbWVhbiA9IGNhbGNfYWNjX3N1YmoobWF0Y2hfbWVhbiwgcGFydF90aW1lcykKYGBgCgpgYGB7ciBjYWxjIG1hdGNoIGFjY3VyYWN5IHVzaW5nIHZhcmlhYmlsaXR5IGZlYXR1cmVzfQptYXRjaF9ybXNzZCA9IGNhbGNfbWF0Y2hfdmVjdG9yKGdwc19jbGVhbjJfcm1zc2RfZmVhdCRzdWJqX21hdF8xLGdwc19jbGVhbjJfcm1zc2RfZmVhdCRzdWJqX21hdF8yKQphY2NfdGltZV9ybXNzZCA9IGNhbGNfYWNjX3RpbWUobWF0Y2hfcm1zc2QscGFydF90aW1lcykKYWNjX3N1Ympfcm1zc2QgPSBjYWxjX2FjY19zdWJqKG1hdGNoX3Jtc3NkLCBwYXJ0X3RpbWVzKQpgYGAKCiMjIyAxMS4gUGVybXV0YXRpb24gVGVzdHMgd2l0aCBOZXcgRmVhdHVyZXMgCgojIyMjIDExYS4gQXZlcmFnZSBBY2N1cmFjeQpgYGB7ciBkZWZpbmUgbmV3IHBlcm11dGF0aW9uIGZ1bmN0aW9uc30KcGVybV92ZWN0b3IgPSBmdW5jdGlvbihncHNfZGYsIHBlcm1fdGltZSwgbWV0aG9kKXsKICBncHNfZGZfcGVybSA9IGdwc19kZgogIHBlcm1fYWNjX3RpbWUgPSBsaXN0KCkKICBwZXJtX2FjY19zdWJqID0gbGlzdCgpCiAgZm9yIChpIGluIDE6cGVybV90aW1lKSB7CiAgICBwZXJtX3BhcnRfdGltZXMgPSAxCiAgICBwcmludChwYXN0ZSgicHJvY2Vzc2luZyAuLi4iLCBpLCIuLi4iKSkKICAgIGdwc19kZl9wZXJtJElJRCA9IHNhbXBsZShncHNfZGZfcGVybSRJSUQpCiAgICBwZXJtX3N1Ympfc2VxID0gbWFrZV9zdWJqX3NlcShncHNfZGZfcGVybSxwYXJ0X3RpbWVzID0gcGVybV9wYXJ0X3RpbWVzKQogICAgaWYgKG1ldGhvZCA9PSAicm1zc2QiKSB7CiAgICAgIHBlcm1fZ3BzID0gbWFrZV9mZWF0dXJlX3Jtc3NkKGdwc19kZl9wZXJtLHBlcm1fc3Vial9zZXEpCiAgICB9IGVsc2UgaWYgKG1ldGhvZCA9PSAibWVhbiIpewogICAgICBwZXJtX2dwcyA9IG1ha2VfZmVhdHVyZV9tZWFuKGdwc19kZl9wZXJtLHBlcm1fc3Vial9zZXEpCiAgICB9CiAgICBwZXJtX21hdF8xID0gcGVybV9ncHMkc3Vial9tYXRfMQogICAgcGVybV9tYXRfMiA9IHBlcm1fZ3BzJHN1YmpfbWF0XzIKICAgIHBlcm1fbWF0Y2hfY29yID0gY2FsY19tYXRjaF92ZWN0b3IocGVybV9tYXRfMSxwZXJtX21hdF8yKQogICAgcGVybV9hY2NfdGltZVtbaV1dID0gY2FsY19hY2NfdGltZShwZXJtX21hdGNoX2NvcixwYXJ0X3RpbWVzID0gcGVybV9wYXJ0X3RpbWVzKQogICAgcGVybV9hY2Nfc3VialtbaV1dID0gY2FsY19hY2Nfc3ViaihwZXJtX21hdGNoX2NvcixwYXJ0X3RpbWVzID0gcGVybV9wYXJ0X3RpbWVzKQogIH0KICByZXR1cm4obGlzdChwZXJtX2FjY190aW1lPSBwZXJtX2FjY190aW1lLHBlcm1fYWNjX3N1YmogPSBwZXJtX2FjY19zdWJqKSkKfQpgYGAKCgpgYGB7ciBydW4gcGVybXV0YXRpb24gZm9yIG1lYW4gZmVhdHVyZXMsIGZpZy53aWR0aD0gNiwgbWVzc2FnZT1GQUxTRX0KI3Blcm1fbWVhbiA9IHBlcm1fdmVjdG9yKGdwc19kZl9jbGVhbjIsIDEwMDAsICJtZWFuIikKCnBfdGltZV9tZWFuID0gaGlzdF9jaHgoYWNjX3RpbWVfbWVhbiwgYmlucyA9IDgsIHRpdGxlID0gcGFzdGUoIk1lYW4gRmVhdHVyZXM6IFxuIEF2ZXJhZ2UgQWNjdXJhY3kgQWNyb3NzIixsZW5ndGgoYWNjX3RpbWVfbWVhbiksIkRhdGEgUGFydGl0aW9ucyIpLCB4YXhpcyA9ICJQcmVkaWN0aW9uIEFjY3VyYWN5IiwgeWF4aXMgPSAiQ291bnQiKQoKcV90aW1lX21lYW4gPSAgaGlzdF9jaHgodW5saXN0KHBlcm1fbWVhbiRwZXJtX2FjY190aW1lKSwgYmlucyA9IDgsIHRpdGxlID0gcGFzdGUoIk1lYW4gRmVhdHVyZXM6IFxuIEF2ZXJhZ2UgQWNjdXJhY3kgQWNyb3NzIixsZW5ndGgocGVybV9tZWFuJHBlcm1fYWNjX3RpbWUpLCJQZXJtdXRhdGlvbnMiKSwgeGF4aXMgPSAiUHJlZGljdGlvbiBBY2N1cmFjeSIsIHlheGlzID0gIkNvdW50IikKCnBfdGltZV9tZWFuICsgcV90aW1lX21lYW4KYGBgCgoKYGBge3IgcnVuIHBlcm11dGF0aW9uIGZvciBybXNzZCBmZWF0dXJlcywgZmlnLndpZHRoPSA2LCBtZXNzYWdlPUZBTFNFfQojcGVybV9ybXNzZCA9IHBlcm1fdmVjdG9yKGdwc19kZl9jbGVhbjIsIDEwMDAsICJybXNzZCIpCgpwX3RpbWVfcm1zc2QgPSBoaXN0X2NoeChhY2NfdGltZV9ybXNzZCwgYmlucyA9IDgsIHRpdGxlID0gcGFzdGUoIlJNU1NEIEZlYXR1cmVzOiBcbiBBdmVyYWdlIEFjY3VyYWN5IEFjcm9zcyIsbGVuZ3RoKGFjY190aW1lX3Jtc3NkKSwiRGF0YSBQYXJ0aXRpb25zIiksIHhheGlzID0gIlByZWRpY3Rpb24gQWNjdXJhY3kiLCB5YXhpcyA9ICJDb3VudCIpCgpxX3RpbWVfcm1zc2QgPSBoaXN0X2NoeCh1bmxpc3QocGVybV9ybXNzZCRwZXJtX2FjY190aW1lKSwgYmlucyA9IDgsIHRpdGxlID0gcGFzdGUoIlJNU1NEIEZlYXR1cmVzOiBBdmVyYWdlIEFjY3VyYWN5IEFjcm9zcyIsbGVuZ3RoKHBlcm1fbWVhbiRwZXJtX2FjY190aW1lKSwiUGVybXV0YXRpb25zIiksIHhheGlzID0gIlByZWRpY3Rpb24gQWNjdXJhY3kiLCB5YXhpcyA9ICJDb3VudCIpCgpwX3RpbWVfcm1zc2QgKyBxX3RpbWVfcm1zc2QKYGBgCgpgYGB7ciBkZWZpbmUgY29tYmluZSBwZXJtIHN1YmogZnVuY3Rpb25zfQoKY29tYmluZV9wZXJtX3N1YmogPSBmdW5jdGlvbihhY2Nfc3Vial9wbG90LCBwZXJtX2FjY19zdWJqKSB7CiAgcGVybV9zdWJqID0gbGlzdCgpCiAgZm9yIChzdWJqIGluIGFjY19zdWJqX3Bsb3QkZGF0YSR4KSB7CiAgICBwZXJtX3N1YmokdmFsW1tzdWJqXV0gPSBzYXBwbHkocGVybV9hY2Nfc3ViaiwgZnVuY3Rpb24ocGVybSkgcGVybVt3aGljaChuYW1lcyhwZXJtKSA9PSBzdWJqKV0pCiAgICBwZXJtX3N1YmokaGlzdFtbc3Vial1dID0gaGlzdF9jaHgocGVybV9zdWJqW1tzdWJqXV0kdmFsLCBiaW5zID0gOCwgdGl0bGUgPSBwYXN0ZShzdWJqLCI6IEFjY3VyYWN5IEFjcm9zcyBcbiIscGVybV90aW1lLCJQZXJtdXRhdGlvbnMiKSwgeGF4aXMgPSAiUHJlZGljdGlvbiBBY2N1cmFjeSIsIHlheGlzID0gIkNvdW50IikKICAgIHBlcm1fc3ViaiRhY2NbW3N1YmpdXSA9IHN1bShwZXJtX3N1YmokdmFsW1tzdWJqXV0pL3Blcm1fdGltZQogIH0KICByZXR1cm4ocGVybV9zdWJqKQp9CgoKc3Vial9zY2F0dGVyX3Blcm0gPSBmdW5jdGlvbihncHNfZGYsYWNjX3N1YmoscGVybV9zdWJqLCBtZXRob2QpewogICAgc3Vial9kZiA8LSBkYXRhLmZyYW1lKHg9dW5pcXVlKGdwc19kZiRJSUQpKQogIHN1YmpfZGYkeSA9IGFjY19zdWJqCiAgc3Vial9kZiR5X3Blcm0gPSB1bmxpc3QocGVybV9zdWJqJGFjYykKICBzdWJqX2RmID0gc3Vial9kZltvcmRlcihzdWJqX2RmJHkpLF0KICBwID0gZ2dwbG90KHN1YmpfZGYsIGFlcyh4ID0gcmVvcmRlcih4LCB5KSwgeSA9IHZhbHVlKSkgKyAKICAgIGdlb21fcG9pbnQoYWVzKHkgPSB5LCBjb2wgPSAic3ViamVjdCBkYXRhIikpICsgCiAgICBnZW9tX3BvaW50KGFlcyh5ID0geV9wZXJtLCBjb2wgPSAicGVybXV0YXRpb24iKSkgKwogICAgdGhlbWVfY293cGxvdCgpICsgCiAgICBsYWJzKHRpdGxlID0gcGFzdGUobWV0aG9kLCJGZWF0dXJlcyBcbiBTdWJqZWN0IExldmVsIEFjY3VyYWN5IEFjcm9zcyIscGFydF90aW1lcywiRGF0YSBQYXJ0aXRpb25zIiksIAogICAgICAgICB4ID0gIlN1YmplY3RzIiwgeSA9ICJQcmVkaWN0aW9uIEFjY3VyYWN5IikgKwogICAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA0NSwgaGp1c3QgPSAxLCBzaXplID0gOCksIHBsb3QudGl0bGUgPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwLjUpKQogIHJldHVybihwKQp9CgpgYGAKCgpgYGB7ciBtZWFuIGZlYXR1cmVzIGJ5IHN1YmplY3Qgd2l0aCBwZXJtdXRhdGlvbn0KcF9zdWJqX21lYW4gPSBzdWJqX3NjYXR0ZXIoZ3BzX2RmX2NsZWFuMiwgYWNjX3N1YmpfbWVhbiwgIk1lYW4iKQpwZXJtX3N1YmpfbWVhbiA9IGNvbWJpbmVfcGVybV9zdWJqKHBfc3Vial9tZWFuLHBlcm1fbWVhbiRwZXJtX2FjY19zdWJqKQpwX3N1YmpfbWVhbl9wZXJtID0gc3Vial9zY2F0dGVyX3Blcm0oZ3BzX2RmX2NsZWFuMiwgYWNjX3N1YmpfbWVhbiwgcGVybV9zdWJqX21lYW4sICJNZWFuIikKZ2dwbG90bHkocF9zdWJqX21lYW5fcGVybSkKYGBgCgpgYGB7ciBybXNzZCBmZWF0dXJlcyBieSBzdWJqZWN0IHdpdGggcGVybXV0YXRpb259CnBfc3Vial9ybXNzZCA9IHN1Ympfc2NhdHRlcihncHNfZGZfY2xlYW4yLCBhY2Nfc3Vial9ybXNzZCwgIlJNU1NEIikKcGVybV9zdWJqX3Jtc3NkID0gY29tYmluZV9wZXJtX3N1YmoocF9zdWJqX3Jtc3NkLHBlcm1fcm1zc2QkcGVybV9hY2Nfc3ViaikKcF9zdWJqX3Jtc3NkX3Blcm0gPSBzdWJqX3NjYXR0ZXJfcGVybShncHNfZGZfY2xlYW4yLCBhY2Nfc3Vial9ybXNzZCwgcGVybV9zdWJqX3Jtc3NkLCAiUk1TU0QiKQpnZ3Bsb3RseShwX3N1Ympfcm1zc2RfcGVybSkKYGBgCgoKIyMjIDEyLiBDb21wYXJlIEZlYXR1cmVzCmBgYHtyIGNvbXBhcmUgYWNyb3NzIGRhdGEgcGFydGl0aW9uLCBmaWcud2lkdGg9OH0KcF90aW1lX2NvciArIHBfdGltZV9tZWFuICsgcF90aW1lX3Jtc3NkCmBgYAoKYGBge3IgY29tcGFyZSBhY3Jvc3Mgc3ViamVjdHMsIGZpZy5oZWlnaHQ9NiwgZmlnLndpZHRoPTR9CnBfc3Vial9jb3JfcGVybSAvIHBfc3Vial9tZWFuX3Blcm0gLyBwX3N1Ympfcm1zc2RfcGVybQpgYGAKCiMjIyAxMy4gQ29tYmluZSBGZWF0dXJlcwoKIyMjIDE0LiBNaXNjIEluZm8KYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KI3Nlc3Npb25JbmZvKCkKYGBgCgo=
 

A work by Cedric Huchuan Xia

hxia@upenn.edu